Skip to main content

10. Same Tree

easyAsked at Tesla

Check whether two binary trees are structurally identical with equal node values.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given roots p and q of two binary trees, return true if the trees have the same structure and equal node values at every position.

Constraints

  • 0 <= node count <= 100
  • -10^4 <= node.val <= 10^4

Examples

Example 1

Input
p = [1,2,3], q = [1,2,3]
Output
true

Example 2

Input
p = [1,2], q = [1,null,2]
Output
false

Approaches

1. Serialize and compare

Serialize both with null markers, compare strings.

Time
O(n)
Space
O(n)
const enc = n => n ? `${n.val},${enc(n.left)},${enc(n.right)}` : 'X';
return enc(p) === enc(q);

Tradeoff:

2. Recursive structural compare

Both null or both non-null with equal values and equal subtrees.

Time
O(n)
Space
O(h)
function isSameTree(p, q) {
  if (!p && !q) return true;
  if (!p || !q) return false;
  if (p.val !== q.val) return false;
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Tradeoff:

Tesla-specific tips

Tesla likes equality checks that bail early — a depth-first short-circuit avoids touching the whole tree, the same way scene-graph diff prunes branches that haven't moved between frames.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Same Tree and other Tesla interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →