Skip to main content

9. Same Tree

easyAsked at SoFi

Given two binary trees, check if they are structurally identical with the same node values — a recursion warm-up SoFi uses when modeling account hierarchy comparison.

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

Problem

Given the roots of two binary trees p and q, write a function to check if they are the same tree. Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Constraints

  • Number of nodes in each tree is in range [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 arrays and compare.

Time
O(n)
Space
O(n)
function isSameTree(p, q) {
  const s = t => t ? [t.val, ...s(t.left), ...s(t.right)] : ['#'];
  return JSON.stringify(s(p)) === JSON.stringify(s(q));
}

Tradeoff:

2. Recursive DFS

Compare nodes pairwise: both null = same, one null = different, vals equal and subtrees equal.

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:

SoFi-specific tips

SoFi values clean base cases for recursion since loan amortization schedules rely on consistent recursion to compute principal/interest splits across months.

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

Practice these live with InterviewChamp.AI →