Same Tree or Not?

Given the root node of two trees, find if they are the same .

For example:

The below trees:

[1,2,3] and [1,2,3] are the same

[1,2] and [1,2,3] are not same.

Note that though the given input is two arrays above, you can’t just compare each value of one array with the other array.

The actual program takes two TreeNode datastructures as input.

Try out the solution here:

https://leetcode.com/problems/same-tree/

Solution:

Use Depth First Search or Breadth First Search

Approach 1 – Depth First Search:

Recursively compare each node value in the tree.

Here is the code:

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

As you see,

If both nodes are null then they are still the same so you return true

If either of them are null then they are not equal so return false.

If their values are not equal then they are not equal so return false.

Else if their values are equal , then you compare their left and right nodes as above recursively.

If both of them are equal return true else false.

Algorithm:

1. If both nodes are null return true
2. If any of the nodes are null return false
3. If the value of the nodes are not equal return false
4. Check recursively if the left and right nodes are equal and return the result

Time complexity:

Since we traverse each node time complexity is O(n) where n is the number of nodes

Space complexity:

At the worst case we make a recursive call for every node so space complexity is O(n)

Approach 2 – Breadth First Search

In this approach we use queues instead of recursion

Initially you put the two given two nodes into a queue.

Then you do the below logic:

While queue is not empty:

1. Pop the first two nodes

2. If both of them are null then go back to the previous step (pop the next two nodes)

3. If just one of them is null return false

4. If their values are not equal return false

5. If their values are equal then we need to look into the left and right child nodes of the current node of both trees, so put them in the queue.

In step 2 , instead of returning true , we are continuing from step 1 .

We do this because consider the use case:

The left child of the current nodes of both the trees are null

But the right child of both the trees have values

So while popping from the queue in case you have popped the left child of both the trees(null) , then you need to ignore them and pop the next two (right child of both the trees will be in the top of the queue now).

If you return true seeing that both of them are null and then if the right children are not equal then the result is invalid.

Here is the code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        
        
      
        
        
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        
        queue.add(p);
        queue.add(q);
        
        
        while(!queue.isEmpty()){
            
            
            TreeNode a = queue.poll();
            
            TreeNode b = queue.poll();
            
    
            if(a == null && b == null) continue;
        
           
            if(a == null || b== null ) return false;
            
            
         
        
            if(a.val != b.val) return false;
          
            
            queue.add(a.left);
            queue.add(b.left);
            queue.add(a.right);
            queue.add(b.right);
          
            
        }
        
        
        return true;
        
    }
}

Time complexity:

You traverse each node once so time complexity is O(n)

Space complexity:

You put each node in the queue in the worst case (the tree is equal) , so space complexity is O(n)

that’s it!