Skip to main content

10. Same Tree

easyAsked at Etsy

Decide if two trees are structurally and value-wise identical — Etsy uses it to test recursion clarity.

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

Problem

Given roots of two binary trees p and q, write a function to check if they are the same — same structure and same node values.

Constraints

  • Node counts in [0, 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

DFS both trees into strings with null markers, then compare.

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

Tradeoff:

2. Parallel recursion

Recurse on both trees simultaneously, comparing nodes and children.

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

Tradeoff:

Etsy-specific tips

Etsy hires people who handle null cases out loud first — verbalize the (null, null), (null, x), (x, null) split before you write code.

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

Practice these live with InterviewChamp.AI →