Same Tree

Introduction

The Same Tree problem is a classic binary tree question commonly encountered in coding interviews and programming competitions. The problem involves determining if two binary trees are identical, meaning they have the same structure and node values.

Problem Description

Given the roots of two binary trees, p and q, the task is to check if the two trees are structurally identical and have the same values at every corresponding node.

Example

Consider the following two binary trees:

Tree 1:

            1
           / \
          2   3
        

Tree 2:

            1
           / \
          2   3
        

Here, the trees are identical, so the output is true.

Tree 3:

            1
           / \
          2   4
        

For Tree 1 and Tree 3, the output is false because the right child values differ.

Approach

The Same Tree problem can be solved using recursion. The idea is to compare the root nodes of the two trees, then recursively compare their left and right subtrees. If at any point the nodes differ, we return false.

Steps

1. Check if both nodes are null. If they are, return true.
2. If one of the nodes is null and the other is not, return false.
3. Compare the values of the two nodes. If they differ, return false.
4. Recursively check the left and right subtrees of the nodes.

Implementation in Java

Here is a simple implementation of the Same Tree problem in Java:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // Base case: Both nodes are null
        if (p == null && q == null) {
            return true;
        }
        // One of the nodes is null, or values do not match
        if (p == null || q == null || p.val != q.val) {
            return false;
        }
        // Recursive check for left and right subtrees
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}
        

Complexity Analysis

• Time Complexity: O(n), where n is the total number of nodes in the smaller tree. We visit each node once.
• Space Complexity: O(h), where h is the height of the tree. This is the space used by the recursion stack.

Iterative Solution

An iterative approach can also be used with a queue for breadth-first traversal:

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

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

        while (!queue.isEmpty()) {
            TreeNode t1 = queue.poll();
            TreeNode t2 = queue.poll();

            if (t1 == null && t2 == null) {
                continue;
            }
            if (t1 == null || t2 == null || t1.val != t2.val) {
                return false;
            }

            queue.add(t1.left);
            queue.add(t2.left);
            queue.add(t1.right);
            queue.add(t2.right);
        }

        return true;
    }
}
        

Applications

The Same Tree problem has practical applications in various fields:

• Data Validation: Comparing database schemas or file structures.
• Version Control: Checking if two versions of a data structure are identical.
• Game Development: Verifying if two game states are identical for replay systems.

Common Pitfalls

• Forgetting to check for null nodes can result in a NullPointerException.
• Mixing up recursive calls for left and right subtrees.
• Not handling edge cases like empty trees.

Edge Cases

• Both trees are empty (return true).
• One tree is empty, and the other is not (return false).
• Trees with different structures but the same values (return false).

Conclusion

The Same Tree problem is an excellent example of recursion in action. It helps in understanding tree traversal and comparison techniques. By practicing this problem, one gains a deeper insight into binary trees and their applications in computer science.