Same Tree

Recurse on both trees in lockstep

time O(n)space O(h)

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.

Details

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.

Problem:Same TreeEasy

Recurse on both trees in lockstep

step 1 / 13

p|q

Call stack

same(1, 1)

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

Every step in words

Show all 13 steps

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.
Compare the pair (2, 2): 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 (4, 4) first, then the right ones.
Compare the pair (4, 4): 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 (null, null) first, then the right ones.
The left children of 4 and 4 are both null. Two missing subtrees are identical, so this call returns true — a null is only a problem when the OTHER tree has a node there.
The right children of 4 and 4 are both null. Two missing subtrees are identical, so this call returns true — a null is only a problem when the OTHER tree has a node there.
Both subtrees under (4, 4) matched, so same(4, 4) returns true and its frame pops. This pair is now settled — the parent still has its other side to check.
The right children of 2 and 2 are both null. Two missing subtrees are identical, so this call returns true — a null is only a problem when the OTHER tree has a node there.
Both subtrees under (2, 2) matched, so same(2, 2) returns true and its frame pops. This pair is now settled — the parent still has its other side to check.
Compare the pair (3, 3): 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 (null, 5) first, then the right ones.
Structural mismatch: on the left of 3, tree q has a node 5 but the other tree has null. Same shape is required before values even matter, so this call returns false immediately.
The left comparison under 3 came back false, so AND short-circuits: the right children (5, null) are never visited. same(3, 3) returns false to same(1, 1).
The right comparison under 1 came back false, so same(1, 1) returns false — the final answer.
Answer: false. p = [1,2,3,4,null,null,5] and q = [1,2,3,4,null,5] share every value, yet one node sits on a different side, and the recursion stopped at the first pair that disagreed. Every node is visited at most once, so the cost is O(n) time and O(h) stack.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Same Tree in the editor All Binary Trees problems Back to roadmap