100. Same Tree

Return true if two binary trees have the same structure and the same node values.

Walk both trees in lockstep with a queue of node pairs, comparing each pair.

1function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
2  const queue: [TreeNode | null, TreeNode | null][] = [[p, q]];
3  while (queue.length) {
4    const [a, b] = queue.shift()!;
5    if (!a && !b) continue;
6    if (!a || !b || a.val !== b.val) return false;
7    queue.push([a.left, b.left], [a.right, b.right]);
8  }
9  return true;
10}

p

q

queue of pairs

1|1

Queue the root pair.

1 / 0

Space: play/pause · ←/→: step