Skip to main content

9. Same Tree

easyAsked at MercadoLibre

Decide whether two binary trees are structurally identical with 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 the trees are the same. Two trees are the same when they are structurally identical and the nodes have the same values at matching positions.

Constraints

  • 0 <= node count <= 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 both trees to strings and compare.

Time
O(n)
Space
O(n)
const serialize = (n) => n ? `${n.val},${serialize(n.left)},${serialize(n.right)}` : '#';
return serialize(p) === serialize(q);

Tradeoff:

2. Parallel DFS

Walk both trees together; bail out as soon as a structural or value mismatch appears.

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:

MercadoLibre-specific tips

MercadoLibre uses this as a baseline check for catalog dedupe logic — they want to see a short-circuit DFS instead of a full serialize compare across millions of listings.

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

Practice these live with InterviewChamp.AI →