100. Same Tree (Easy)

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

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

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

Solution 1: Recursive, preorder traversal O(n); O(h)

Base cases: check null. Then compare the value between p and q. If not equal, return false, if equal, recursively check left and right children.

    public boolean isSameTree(TreeNode p, TreeNode q) {
        //if (p == null || q == null) return p == q; //equal to the following 2 if blocks
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;

        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

Solution 2: Iterative + Stack O(n); O(h)

First, push 2 root nodes into stack, then pop 2 nodes from stack, check if current nodes are equal, if not equal, return false, if equal, push the left and right children of current nodes into stack. Repeat until the stack is empty.

    public boolean isSameTree(TreeNode p, TreeNode q) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(p); //Push two root nodes into stack 
        stack.push(q);

        while (!stack.isEmpty()) {
            TreeNode qn = stack.pop();
            TreeNode pn = stack.pop(); //check null after poping from stack
            if (qn == null && pn == null) {
                continue;
            }
            if (qn == null || pn == null || qn.val != pn.val) {
                return false;
            }
            stack.push(pn.left);
            stack.push(qn.left);
            stack.push(pn.right);
            stack.push(qn.right);
        }
        return true;
    }