Skip to main content

5. Same Tree

easyAsked at Baidu

Decide whether two binary trees are structurally identical and hold the same values at every node.

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 tree. Two binary trees are the same when they are structurally identical and the corresponding nodes hold 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 both trees to strings with explicit null markers, compare strings.

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

Tradeoff:

2. Parallel DFS

Recurse on both trees in lockstep; bail on first mismatch in structure or value.

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:

Baidu-specific tips

Baidu compares crawler-frontier sub-trees to detect duplicate page hierarchies, so they reward an early-exit DFS over any serialize-and-compare hack.

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

Practice these live with InterviewChamp.AI →