The question that I will present here is called “Same Tree” and it also is available here.

We need to implement the function isSameTree which receives two trees and must return a boolean answering if they have the same values, and they are also structually equal.

We may solve this question recursively or iteratively. For any way to solve this problem, we can point out three scenarios:

1. Both trees p and q are null
2. Tree p or tree q is null, and the other are not
3. Both trees p and q are not null

First, let’s get a look on the recurve way to do this.

public boolean isSameTree(TreeNode p, TreeNode q) {
    // Scenario 1
    if (p == null && q == null) 
        return true;

    // Scenario 2
    if (p == null || q == null) 
        return false;

    // Scenario 3
    if (p.val == q.val)
        return isSameTree(p.left, q.left) && 
            isSameTree(p.right, q.right);
    return false;
}

For iterative solution, I created two stacks to help storing the subtrees of the both trees that we received as arguments, and check whenever they are equal (their values inside the node), if they are not equal or we find scenario 2, where a subtree is null and the other is not, we are sure that both trees are not equal. Let’s have a look on the code then.

public boolean isSameTree(TreeNode p, TreeNode q) {
    // Scenario 1
    if (p == null && q == null) return true;
    
    // Scenario 2
    if (p == null || q == null) return false;
    
    // Scenario 3
    Stack<TreeNode> s1 = new Stack<>();
    Stack<TreeNode> s2 = new Stack<>();
    
    s1.push(p);
    s2.push(q);
    
    while (!s1.isEmpty() && !s2.isEmpty()) {
        TreeNode t1 = s1.pop();
        TreeNode t2 = s2.pop();
        
        if (t1.val != t2.val) return false;
        
        if (t1.left != null && t2.left != null) {
            s1.push(t1.left);
            s2.push(t2.left);
        } else if (t1.left != null || t2.left != null)  
            return false;
        
        if (t1.right != null && t2.right != null) {
            s1.push(t1.right);
            s2.push(t2.right);
        } else if (t1.right != null || t2.right != null)  
            return false;
    }
    
    return true;
}

Strictly speaking, the approach for iteratively way to solve this problem is called Depth First Search (DFS), as we start at the root and go deeper into the left side until the maximum we can go (meaning finding an null node), and then go to the right side. This is obviously not the only way to do this, we can change the Stack for an Queue, and perform a Breath First Search (BFS) which goes for all nodes at the same level, then to the next level. The code to solve either DFS or BFS is pretty similar though, but I will leave to the reader to check this out.

Any further questions, do not hesitate to send an email to me! Stay tuned! :)