Same Tree: check if two trees are identical

• Same Tree checks whether two binary trees are identical in both shape and node values.
• Parallel recursion walks both trees in lockstep, visiting corresponding positions together.
• Both-null at a position means it matches; one-null means the structures diverge.
• Short-circuit AND collapses the result to false on the first mismatch in shape or value.
• Time is O(min(n1, n2)) because a mismatch halts early; space is O(h) for the call stack.

What is the Same Tree problem?

Same Tree asks whether two binary trees are structurally identical and have the same value at every corresponding node. It is a fundamental recursive comparison that forms the basis for subtree matching, tree equality checks, and hierarchy auditing.

package com.bank.service;

public class HierarchyAuditService {
    public boolean isSameTree(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;
        if (a == null || b == null) return false;
        return a.val == b.val
            && isSameTree(a.left, b.left)
            && isSameTree(a.right, b.right);
    }
}

Why does this problem matter?

In banking systems, two independent systems may maintain the same approval hierarchy. Before an audit, the compliance team verifies that the two trees match exactly. A silent divergence could mean an unauthorized approver was inserted, so the lockstep comparison fails fast on the first difference and raises a severe alert.

How does the parallel recursion work?

The recursion walks both trees simultaneously. At each position there are four possible states:

1. Both nodes are null: this position matches, return true.
2. One node is null and the other is not: structures differ, return false.
3. Both nodes exist but values differ: return false.
4. Both nodes exist with equal values: recurse into both left subtrees and both right subtrees.

// Detailed step-by-step
public boolean isSameTree(TreeNode a, TreeNode b) {
    // Case 1: both null, positions match
    if (a == null && b == null) return true;

    // Case 2: one null, structures diverge
    if (a == null || b == null) return false;

    // Case 3: values differ
    if (a.val != b.val) return false;

    // Case 4: recurse into subtrees
    return isSameTree(a.left, b.left)
        && isSameTree(a.right, b.right);
}

Tree A:     1        Tree B:     1
           / \                  / \
          2    3               2    3

Compare(1,1): values match
  Compare(2,2): values match
    Compare(null,null): true
    Compare(null,null): true
  Compare(3,3): values match
    Compare(null,null): true
    Compare(null,null): true
Result: true

Why does the order of null checks matter?

The both-null check must come before the one-null check. If you reverse them, the one-null check would catch the both-null case first and incorrectly return false.

// WRONG ORDER: both-null is caught by one-null check
if (a == null || b == null) return false;  // both-null returns false!
if (a == null && b == null) return true;   // never reached

// CORRECT ORDER:
if (a == null && b == null) return true;   // both-null first
if (a == null || b == null) return false;  // then one-null

How is Same Tree different from Symmetric Tree?

Same Tree checks if two separate trees are identical. Symmetric Tree checks if a single tree is a mirror image of itself. The recursion for symmetric compares left-of-left with right-of-right and right-of-left with left-of-right.

| Aspect | Same Tree | Symmetric Tree |
|--------|-----------|----------------|
| Input | Two separate trees | One tree |
| Comparison | Corresponding positions | Mirror positions |
| Recursive call | same(a.left, b.left) | sym(a.left, b.right) |
| Use case | Verify two copies match | Check if tree is a mirror |

What are edge cases?

• Both trees empty (null): return true.
• One tree empty, the other not: return false.
• Trees with same values but different structures: return false.
• Single-node trees with matching values: return true.

// Edge case: same values, different structure
// Tree A:  1       Tree B:  1
//         /                  \
//        2                    2
// Result: false (structures differ)

What are common mistakes?

Using reference equality (==) instead of .equals() for object-valued nodes. For primitive int values, == works correctly. For Integer or String node values, == compares references, not values, which can give wrong results due to autoboxing or interning.

// WRONG for object values:
if (a.val == b.val) // compares references for objects

// CORRECT for object values:
if (a.val.equals(b.val)) // compares actual values

// For primitive int, == is correct:
if (a.val == b.val) // works fine for int

What about an iterative approach?

You can use two queues (or two stacks) to process both trees in lockstep iteratively. Enqueue both roots, then repeatedly dequeue a pair, compare them, and enqueue their children as pairs. This avoids deep recursion on skewed trees.

public boolean isSameTreeIterative(TreeNode a, TreeNode b) {
    java.util.Queue<TreeNode> queue = new java.util.LinkedList<>();
    queue.offer(a);
    queue.offer(b);
    while (!queue.isEmpty()) {
        TreeNode n1 = queue.poll();
        TreeNode n2 = queue.poll();
        if (n1 == null && n2 == null) continue;
        if (n1 == null || n2 == null) return false;
        if (n1.val != n2.val) return false;
        queue.offer(n1.left);
        queue.offer(n2.left);
        queue.offer(n1.right);
        queue.offer(n2.right);
    }
    return true;
}

What should a senior engineer know?

The short-circuit AND means that on average the comparison terminates well before visiting all nodes when the trees differ. In the worst case (identical trees), every node is visited once, giving O(n) time. The space is O(h) for the recursion stack.

For production hierarchy auditing at the National Bank of India, Rajesh added detailed logging at the first mismatch point, recording the position, the expected value, and the actual value, so the compliance team could pinpoint exactly where the two hierarchies diverged without manually inspecting every node.