Blind 75Easy

Same Tree — Parallel DFS Comparison

Traverse both trees simultaneously; if nodes mismatch in structure or value, return false.

TreeDFS

View problem on LeetCode

Problem Statement

Determine if two binary trees are structurally identical with equal node values.

Why This Problem Matters

Foundational tree comparison pattern reused in many problems.
Becomes a helper for subtree, symmetry, and equality checks.
Tests ability to reason about recursion termination precisely.

Thought Process

Compare nodes pairwise

If both null return true; if one null or values differ return false.

Recurse on children

Evaluate left subtrees then right subtrees; both must match.

Consider iterative stack alternative

Two stacks or queues can perform parallel traversal iteratively.

Step-by-Step Reasoning

If p and q both null, return true.
If one null or p.val != q.val, return false.
Recursively compare left children and right children.

Dry Run

Identical small trees

Recursion returns true for all nodes.

One tree missing a leaf

Mismatch detected when one branch hits null earlier.

Complexity Analysis

Time

O(n)

Space

O(h)

Why

Touch each node once; recursion depth depends on height.

Annotated Solution

JAVA

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

  public static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
  }
}

Parallel recursion keeps structure and value checks simple and declarative.

Common Pitfalls

Comparing references instead of values in languages where nodes may differ.
Neglecting to check right subtree if left already fails wastes time—short-circuit results.
Mixing up tree parameters in recursive calls.

Follow-Up Questions

How would you determine if two trees are mirror images?
Can you serialise both trees and compare strings instead?

Key Takeaways

Tree comparison templates are worth memorising.

Short-circuit evaluation saves time on mismatches.

Iterative versions exist but recursion is easiest to present.