Same Tree

Why it belongs on this sheet

This is a clean structural recursion problem and good practice for comparing two traversals in lockstep.

Pattern

Parallel DFS

Approach

Two trees are the same only if both current nodes are null, or both exist with equal values and matching left and right subtrees.

Java solution

class Solution {
  public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null || q == null) {
      return p == q;
    }

    return p.val == q.val
      && isSameTree(p.left, q.left)
      && isSameTree(p.right, q.right);
  }
}

Complexity

• Time: O(n)
• Space: O(h)

Interview note

A strong verbal model is: "compare node, compare left, compare right."