Pattern visualizer

Same Tree

Two trees are the same when their roots agree AND their left subtrees are the same AND their right subtrees are the same — the definition is already recursive. Walk both trees together, one pair of nodes per call: a null on one side with a node on the other is a shape mismatch, which is exactly what a traversal without null markers would miss. Animated on: Are p = [1,2,3,4,null,null,5] (left) and q = [1,2,3,4,null,5] (right) the same tree? Expected false..

Recurse on both trees in lockstep

time O(n)space O(h)step 1 / 13

p|q

Call stack

same(1, 1)

line 8

Compare the pair (1, 1): both exist and the values match. That alone proves nothing about the subtrees, so the frame parks on the stack and the SAME recursion runs on the left children (2, 2) first, then the right ones.

Pseudocode

1FUNCTION isSameTree(p, q):
2  IF p = null AND q = null:
3    RETURN true
4  IF p = null OR q = null:
5    RETURN false
6  IF p.val != q.val:
7    RETURN false
8  RETURN isSameTree(p.left, q.left) AND isSameTree(p.right, q.right)

← / → step · space play · Home restart

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap