Skip to main content

6. Same Tree

easyAsked at Mercury

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

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 tree. Two trees are the same when their structure matches and every corresponding node has the same value.

Constraints

  • Node count 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. Iterative BFS pair queue

Push both roots, pop pairs, compare values and shape.

Time
O(n)
Space
O(n)
const q=[[p,q]];
while(q.length){const [a,b]=q.shift();
  if(!a&&!b) continue; if(!a||!b||a.val!==b.val) return false;
  q.push([a.left,b.left],[a.right,b.right]);}
return true;

Tradeoff:

2. Recursive structural compare

Base cases handle null pairs and mismatched shape; recurse on both children. Clean, O(n) stack-bounded.

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:

Mercury-specific tips

Mercury uses this shape to test ledger snapshot comparators — frame the recursion as verifying two account-tree snapshots match across multi-account aggregation views.

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

Practice these live with InterviewChamp.AI →