Frontend Beauty
ESC

Type to search the knowledge base.

Same Tree

Check if two binary trees are identical in structure and values — recursive DFS or BFS pair walk.

beginner3 min read
  • dsa
  • tree
  • interview
  • Google
  • Meta

The problem

Given roots of two binary trees p and q, return whether they are the same: identical structure and node values.

  1         1
 / \       / \
2   3     2   3   → true

  1         1
 /           \
2             2   → false

Node shape

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

Brute force

Serialize both trees to strings and compare. Works; wastes space and hides the recursive structure interviewers want.

function serialize(root: TreeNode | null): string {
  if (!root) return "#";
  return `${root.val},${serialize(root.left)},${serialize(root.right)}`;
}
function isSameTreeSerialize(p: TreeNode | null, q: TreeNode | null): boolean {
  return serialize(p) === serialize(q);
}

Optimal: simultaneous DFS

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  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);
}

BFS with a queue of pairs:

function isSameTreeBfs(p: TreeNode | null, q: TreeNode | null): boolean {
  const queue: [TreeNode | null, TreeNode | null][] = [[p, q]];
  while (queue.length) {
    const [a, b] = queue.shift()!;
    if (!a && !b) continue;
    if (!a || !b || a.val !== b.val) return false;
    queue.push([a.left, b.left], [a.right, b.right]);
  }
  return true;
}
Time O(n) — n = min nodes until mismatch / all nodes
Space O(h) recursion or O(n) queue

Edge cases

  • Both null → true
  • One null → false
  • Same shape, different values
  • Mirror images are not the same (that’s a different problem)

Common bugs

  • Checking values before null structure
  • Comparing only preorder values without null markers
  • Treating mirrors as equal

Interview delivery

  1. Null/null, xor null, values, recurse both sides.
  2. Code the four-liner.
  3. O(n).
  4. Bridge to Subtree of Another Tree.

Structural cases table

p q result
null null true
null node false
node null false
vals differ false
else recurse both sides

Encode that table as the first four lines of your function — interviewers love the clarity.

Why serialization needs nulls

Preorder values 1,2,3 could be left-child 2 or right-child 2. Null markers disambiguate. Same Tree DFS compares structure on the fly without building strings.

Mirror confusion

“Symmetric tree” asks left/right mirrors. Same Tree asks exact equality. Don’t mix the recursive calls (left with right vs left with left).

Further reading