100. Same Tree

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:

Method 1: recursive

Implementation is straightforward.

We recursively check whether the nodes at same position in two trees are identical.



Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
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);
    }
}

Method 2: iterative

The ideas is to use stack to store nodes from two trees. And every time we pop two of them and compare the value. We are comparing the nodes from two trees at the same position.

When we push, we push the left node of p and left node of q, or we push the right node of p and right node of q.

The nodes are pushed into the stack in pairs, so if the size of stack mod 2 is not zero, it must not be identical.


Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Stack<TreeNode> stack = new Stack<>();
        if (!addNode(p, q, stack)) {
            return false;
        }
        while (!stack.isEmpty()) {
            if (stack.size() % 2 != 0) {
                return false;
            }
            p = stack.pop();
            q = stack.pop();
            if (p.val != q.val) {
                return false;
            }
            if (!addNode(p.left, q.left, stack)) {
                return false;
            }
            if (!addNode(p.right, q.right, stack)) {
                return false;
            }
        }
        return true;
    }
    
    public boolean addNode(TreeNode p, TreeNode q, Stack<TreeNode> stack) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        stack.push(p);
        stack.push(q);
        return true;
    }
}