Skip to main content

9. Same Tree

easyAsked at Nubank

Determine whether two binary trees are structurally identical with equal node values, a classic recursion warm-up Nubank uses to check candidates can write clean base cases before any LatAm payments-domain follow-up.

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

Problem

Given the roots of two binary trees p and q, return true if and only if they are the same tree. Two trees are the same if they are structurally identical and all corresponding nodes have equal values.

Constraints

  • Number of nodes in each tree is 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. Brute force serialize-and-compare

Serialize both trees to strings and compare.

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

Tradeoff:

2. Recursive structural compare

Walk both trees simultaneously, return false on first mismatch. Avoids the serialization allocation.

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:

Nubank-specific tips

Nubank engineers prefer the recursive version; mention how you'd extend this to compare ledger snapshots across replicas for instant-payments (PIX) reconciliation.

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

Practice these live with InterviewChamp.AI →