Skip to main content

10. Same Tree

easyAsked at GitLab

Check 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, return true if they have the same shape and the same node values at every position; false otherwise.

Constraints

  • 0 <= nodes <= 100
  • -10^4 <= 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

Pre-order serialize both with null markers and compare strings.

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

Tradeoff:

2. Recursive walk

Both null OK; one null fails; otherwise vals equal and recurse.

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:

GitLab-specific tips

GitLab might pivot this to diffing two merge-request branches — be ready to discuss how you'd report the first divergence path.

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

Practice these live with InterviewChamp.AI →