Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Problem

Same Tree

LeetCode #100Easy

Lockstep pre-order DFS over both trees

Given the roots of two binary trees p and q, return true if they are structurally identical and every corresponding pair of nodes has the same value.

Asked atAmazonGoogleBloomberg

Recursive lockstep DFS

time O(n)space O(h)

step 1 / 12

tree p (q shown as ✓ notes)

call stack ↓

(returned)

Recursive lockstep DFS


▸
1same(p, q):
2    if p is null and q is null: return true   // both empty → fine
3    if p is null or q is null:  return false  // shape differs
4    if p.val != q.val:          return false  // value differs
5    return same(p.left, q.left) AND same(p.right, q.right)
6// answer = same(p, q)

state

goalp ≡ q ?
strategylockstep DFS

line 1Same Tree: are p and q structurally identical AND value-for-value equal? The trick is to walk BOTH trees in lockstep, one pre-order pass: compare the two roots, then recurse left-with-left and right-with-right. We draw tree p; for each p-node we annotate it with the value of the q-node sitting in the same position. A ✓ note means the two matched at that spot.