Skip to main content

10. Same Tree

easyAsked at Unity

Decide if two binary trees are structurally identical. Unity uses this for scene-graph diffing during incremental rebuilds.

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

Problem

Given the roots of two binary trees p and q, return true if they are structurally identical with the same node values.

Constraints

  • 0 <= nodes <= 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 + compare

Serialize both trees with null markers and compare strings.

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

Tradeoff:

2. Recursive structural compare

Both null is equal; one null is unequal; otherwise val matches and both subtrees match.

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

Tradeoff:

Unity-specific tips

Unity grades for early-exit short-circuits because scene-graph diffs on big hierarchies must bail the instant they spot a mismatch.

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 Unity interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →