1. Introduction

Given the roots of two binary trees p and q, write a function to check if they are the same or not.  We consider two binary trees the same if they are structurally identical, and the nodes have the same value.

2. Content

I will discuss 2 different ways to identify if two binary trees are structurally identical and have nodes with the same values or not. I will explore recursive and iterative ways along with their time and space complexity.

Method signature for checking if two trees are the same or not.

public boolean isSameTree(TreeNode p, TreeNode q) {

}

Example 1: Below trees are the same.

Example 2: Below trees are not the same.

Example 3: Below trees are not the same.

3. Check if 2 trees are the same using Recursion

1. First, we need to handle most basic conditions, i.e. nulls and checking for the same values of both trees.

public boolean isSameTree(TreeNode p, TreeNode q) {
        
        if(p == null && q == null) return true;
        
        if(p == null || q == null) return false;
        
        if(p.val != q.val) return false;
}

2. Now we need to iterate for the left and right subtree for both trees and check for their values.

public boolean isSameTree(TreeNode p, TreeNode q) {
        
    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);
        
}

That’s it.

n is the total number of nodes in the tree.

h is the height of the tree.

Time Complexity: O(n) as we need to check for all nodes exactly once.

Space Complexity: Best case O(h) or O(log n) if the tree is balanced. In case of an unbalanced tree, the space complexity is O(n) to keep the recursion stack.

4. Check if 2 trees are the same using Iteration

1. Let us first write the base condition.

public boolean isSameTree(TreeNode p, TreeNode q) {
    if(p == null && q == null) return true;
        
    if(p == null || q == null) return false;

}

2. In order to solve this using iteration we need to use an auxiliary data structure to traverse both the trees.

private boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        
        if(p == null || q == null) return false;
        
        Deque<TreeNode> deq = new LinkedList<>();
        deq.add(p);
        deq.add(q);
}

3. Now comes the interesting part. We just iterate on the queue by removing two elements from the queue and check the values of those elements.

while(!deq.isEmpty()) {
    p = deq.poll();
    q = deq.poll();
    // If both the elements are null, then check for remaining elements.
    if(p == null && q == null) continue;
            
    if(!isValid(p, q)) {
        return false;
    }
    deq.add(p.left);
    deq.add(q.left);
    deq.add(p.right);
    deq.add(q.right);
}

private boolean isValid(TreeNode p, TreeNode q) {
    // If either of the elements is null, then both 
    // trees are not the same.
    if(p == null || q == null) return false;
    // If the values of elements don’t match, then both 
    // trees are not the same.
    if(p.val != q.val) return false;
    return true;
}

4. Entire implementation

    private boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        
        if(p == null || q == null) return false;
        
        Deque<TreeNode> deq = new LinkedList<>();
        deq.add(p);
        deq.add(q);
        
        while(!deq.isEmpty()) {
            p = deq.poll();
            q = deq.poll();
            
            if(p == null && q == null) continue;
            
            if(!isValid(p, q)) {
                return false;
            }
            deq.add(p.left);
            deq.add(q.left);
            deq.add(p.right);
            deq.add(q.right);
        }
        return true;
    }
    
    private boolean isValid(TreeNode p, TreeNode q) {
        if(p == null || q == null) return false;
        if(p.val != q.val) return false;
        return true;
    }

Time Complexity: O(n) as we need to check for all nodes exactly once.

Space Complexity: Best case O(h) or O(log n) if the tree is balanced. In case of unbalanced tree space complexity is O(n) to keep the Deque.

5. Conclusion

In this article, we saw how we check if two trees are structurally identical, with the same node values using recursion and iteration.

GitHub Link: https://github.com/savanibharat/justamonad-tutorials/blob/master/justamonad-tutorials-leetcode/src/main/java/com/justamonad/tutorials/leetcode/tree/SameTree.java