Skip to main content

9. Same Tree

easyAsked at Riot Games

Compare two binary trees node-by-node — a recursion warm-up before Riot dives into client/server state-replication problems.

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. They are the same if they are structurally identical and the nodes have the same value.

Constraints

  • 0 <= 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. Brute force serialization

Serialize both trees and 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. Recursive structural compare

Recurse left and right subtrees simultaneously, short-circuiting on any mismatch. Mirrors how Riot diffs authoritative server state against a client snapshot for replication.

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:

Riot Games-specific tips

Riot favors candidates who reason about structural diffs the same way the game server diffs authoritative state against client predictions during lag compensation.

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

Practice these live with InterviewChamp.AI →