Same Tree

Same Tree

You are given the roots of two binary trees, p and q. Your task is to determine whether the two trees are the same.

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

Example

Input:

p = [1, 2]
q = [1, null, 2]

Output:

false

Constraints

• The number of nodes in both trees is in the range [0, 100].

• -10^4 <= Node.val <= 10^4

Best Data Structure for the Job

Trees are already built using the classic TreeNode class.

We just need:

• A recursive function to traverse both trees in parallel.

Different Approaches

Approach 1: Recursive (Depth-First Search)

We traverse both trees simultaneously using recursion. At every node, we compare the values and recursively compare the left and right subtrees.

/**
 * 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);
    }
}

Approach 2: Iterative (Using Queue)

We perform a simultaneous level-order traversal (BFS) using a queue. At each step, we compare the current pair of nodes, and enqueue their children for further comparison.

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(p);
        queue.offer(q);

        while (!queue.isEmpty()) {
            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();

            if (node1 == null && node2 == null) continue;
            if (node1 == null || node2 == null) return false;
            if (node1.val != node2.val) return false;

            queue.offer(node1.left);
            queue.offer(node2.left);
            queue.offer(node1.right);
            queue.offer(node2.right);
        }

        return true;
    }
}

⚠️ Common Pitfalls
Only checking values and not structure.
Forgetting the case where one tree has more nodes than the other.
Not using recursion when it makes the problem 10x easier.
📊 Complexity Summary
Approach
       Time Complexity
    Space Complexity
Recursive
        O(n)
        O(h) (call stack)
Iterative (Queue)
        O(n)
        O(n)
n = number of nodes in the tree
h = height of the tree
🌍 Real-World Use Cases
Checking backup consistency between two databases stored as trees
Detecting differences in version control systems (AST-based diffing)
Comparing directory structures in file systems

I hope you found this article insightful! Keep exploring, keep learning, and don’t forget to check back daily for more exciting problem breakdowns. If you know someone who would benefit from this, share it with them and help them grow too! That’s it for today—see you in the next post!
                                                                                                                                         Signing off!! 
                                                                                                Master DSA One Problem at a Time :)