Skip to main content

10. Same Tree

easyAsked at DigitalOcean

Determine if two binary trees are structurally and value-wise identical — DigitalOcean uses this to test recursive equality logic that maps to comparing droplet config snapshots across regions.

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 — same structure and same values at every node.

Constraints

  • 0 <= number of nodes <= 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 both

Pre-order serialize each tree to a string with null markers, compare.

Time
O(n+m)
Space
O(n+m)
function ser(n){return n? n.val+','+ser(n.left)+','+ser(n.right) : '#'}
return ser(p)===ser(q);

Tradeoff:

2. Recursive node-pair compare

If both null, equal; if one null, not equal; else compare value and recurse on children.

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:

DigitalOcean-specific tips

DigitalOcean expects you to short-circuit on the first mismatch because config-drift checks across thousands of droplets should fail fast, not serialize the full tree.

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

Practice these live with InterviewChamp.AI →