Skip to main content

10. Same Tree

easyAsked at Yelp

Check whether two binary trees are structurally identical — Yelp uses this as the canonical recursion warmup before diving into category-tree comparison tasks.

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 and corresponding nodes have the same value. Otherwise return false.

Constraints

  • Nodes in each tree are 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

Convert each tree to a string and compare.

Time
O(n)
Space
O(n)
function ser(node) {
  if (!node) return '#';
  return node.val + ',' + ser(node.left) + ',' + ser(node.right);
}
return ser(p) === ser(q);

Tradeoff:

2. Synchronous DFS

Compare values; recurse left and right in lockstep.

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:

Yelp-specific tips

Yelp will follow up by asking how to compare two trees of business categories so equivalent structures don't get duplicated in their taxonomy index.

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

Practice these live with InterviewChamp.AI →