Skip to main content

10. Same Tree

easyAsked at Electronic Arts

Determine whether two binary trees are structurally and value-wise identical.

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

Problem

Given the roots of two binary trees p and q, write a function to check if they are the same. Trees are considered the same if they are structurally identical and node values match.

Constraints

  • 0 <= nodes per tree <= 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

BFS-serialize both trees including nulls and string-compare.

Time
O(n)
Space
O(n)
const ser=r=>{const a=[r];const out=[];while(a.length){const n=a.shift(); if(!n){out.push('#'); continue} out.push(n.val); a.push(n.left,n.right)} return out.join(',')};
return ser(p)===ser(q);

Tradeoff:

2. Recursive structural check

Both null is true; one null is false; otherwise values match and subtrees match.

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

Tradeoff:

Electronic Arts-specific tips

EA cares about cleanly stated base cases — replay-determinism checks in matchmaking depend on consistent recursion termination.

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

Practice these live with InterviewChamp.AI →