Skip to main content

2. Same Tree

easyAsked at Rappi

Decide if two binary trees are structurally identical — Rappi frames this as confirming two dispatch routing trees produce the same courier hand-off sequence.

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

Problem

Given the roots of two binary trees p and q, return true if they are the same. Two trees are the same when both shape and corresponding node values match.

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. Brute force serialize

Serialize both trees to strings and compare.

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

Tradeoff:

2. Recursive structural compare

Walk both trees in lock-step, short-circuiting on the first mismatch in shape or value.

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:

Rappi-specific tips

Rappi expects you to short-circuit on the first mismatch — they'll flag a candidate who serializes both routing trees fully before comparing, since that wastes dispatch latency.

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

Practice these live with InterviewChamp.AI →