Same Tree

Problem

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Solution

Concise Recursion Solution

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        return p.val == q.val ? isSameTree(p.left, q.left) && isSameTree(p.right, q.right) : false;
    }
}

Iterative Stack Solution, Preorder Traversal

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Stack<TreeNode> s1 = new Stack<>(), s2 = new Stack<>();
        if (p != null) s1.push(p);
        if (q != null) s2.push(q);
        while (!s1.isEmpty() && !s2.isEmpty()) {
            TreeNode node1 = s1.pop(), node2 = s2.pop();
            if (node1.val != node2.val) return false;

            if (node1.left != null) s1.push(node1.left);
            if (node2.left != null) s2.push(node2.left);
            if (s1.size() != s2.size()) return false;

            if (node1.right != null) s1.push(node1.right);
            if (node2.right != null) s2.push(node2.right);
            if (s1.size() != s2.size()) return false;
        }
        return s1.size() == s2.size();
    }
}

Analysis

This is a very typical Tree problem
In our recursive solution, we recursively check all the left and right of current TreeNode
The first two lines can be combined with if (p == null || q == null) return p == q;
The iterative solution use preorder traversal to check the identity
We have to check the size of stack as long as we have inserted elements into stack

Complexity:

• Recursion: O(n) time and O(n) space, where n is the height of tree
• Iteration: O(n) time and O(n) space, the worst case happens when given two identical skewed trees