Same Tree

Same Tree

What is this problem about?

The Same Tree interview question asks you to determine whether two binary trees are structurally identical and have the same node values at every corresponding position. Both trees must have the same shape and the same values for the result to be true. This is a fundamental recursive tree comparison problem.

Why is this asked in interviews?

This problem is asked at Apple, Microsoft, Meta, Amazon, LinkedIn, Oracle, Google, Bloomberg, and Adobe as a gateway tree problem. It establishes the template for recursive tree comparison — a pattern reused in problems like Symmetric Tree, Subtree of Another Tree, and comparing BSTs. It tests understanding of simultaneous recursive traversal of two trees.

Algorithmic pattern used

The pattern is simultaneous recursive DFS. Base cases: if both nodes are null → true. If only one is null → false. If values differ → false. Recursive case: return isSameTree(p.left, q.left) and isSameTree(p.right, q.right). Iterative BFS: use a queue of node pairs; for each pair, apply the same checks and enqueue the left and right child pairs.

Example explanation

Tree p: Tree q:

    1               1
   / \             / \
  2   3           2   3

Simultaneous DFS:

• (1, 1): values match. Recurse.
• (2, 2): match. Recurse. Both children null → true.
• (3, 3): match. Recurse. Both null → true.

All comparisons true → return true.

Different trees:

    1               1
   /                 \
  2                   2

• (1,1): match.
• Left: (2, None) → one null → false.

Return false.

Common mistakes candidates make

• Not handling the case where both nodes are None — this is the base case for reaching leaves, and must return true.
• Checking only values without checking structure — both shape AND values must match.
• Forgetting to recurse on both left AND right subtrees — checking only one side misses half the tree.
• Confusing "same tree" with "same BST" — this problem requires identical structure, not just same inorder traversal.

Interview preparation tip

For the Same Tree coding problem, the DFS binary tree interview pattern is the recursive template. The three-line recursive solution is elegant and worth memorizing: check nulls, check values, recurse left and right. Interviewers at Apple and Adobe use this as a warm-up before asking Symmetric Tree or Subtree of Another Tree. Practice both the recursive and iterative (BFS queue of pairs) implementations — knowing the iterative version shows depth of understanding.