Tree day picks up right where grid BFS left off — same snapshot-queue engine, just a different shape of neighbor. Then it branches into BST-specific reasoning: why comparing a node to its parent isn't enough, and how a lowest-common-ancestor search turns out to be the exact same trick as linked list intersection.
102. Level Order Traversal
Read a binary tree floor by floor. This is Rotting Oranges' snapshot trick, just moved from a grid to a tree: take the queue's current length as "everyone on this floor," process exactly that many, and let their children fall into the next floor's batch.
from collections import deque
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
res = []
queue = deque([root])
while queue:
levelSize = len(queue) # snapshot: exactly this floor's nodes
level = []
for _ in range(levelSize):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return resTime: O(n) / Space: O(n)
One difference from grid BFS: no visited needed. A tree has no cycles and exactly one path to every node, so nothing can ever re-enter the queue.
Follow-up: Zigzag Level Order (LC 103)
Same skeleton — only the collected list gets reversed on alternating floors:
if not leftToRight:
level.reverse()
leftToRight = not leftToRightFollow-up: Right Side View (LC 199)
Keep only the last node served on each floor — the rightmost one:
for i in range(levelSize):
node = queue.popleft()
if i == levelSize - 1:
res.append(node.val)
...Follow-up: Average of Levels (LC 637)
Collect a running sum instead of a list — the node count needed for the average is already sitting in levelSize, for free:
levelSum = 0
for _ in range(levelSize):
node = queue.popleft()
levelSum += node.val
...
res.append(levelSum / levelSize)Follow-up: DFS instead of BFS
def dfs(node, depth):
if not node:
return
if depth == len(res):
res.append([])
res[depth].append(node.val)
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)depth == len(res) means "no bucket exists yet for this floor — I'm its first visitor." Visiting left before right keeps each bucket in left-to-right order for free; flipping that order (right first) turns this into Right Side View's DFS solution instead.
Iterative version — mechanical conversion: recursive parameters become a stack tuple, and children get pushed in reverse order (right before left) since a stack flips whatever order you push in:
stack = [(root, 0)]
while stack:
node, depth = stack.pop()
if depth == len(res):
res.append([])
res[depth].append(node.val)
if node.right:
stack.append((node.right, depth + 1))
if node.left:
stack.append((node.left, depth + 1))Worth knowing the number: Python's recursion limit is around 1,000. If the tree could be skewed into a chain with more nodes than that, recursive DFS is a real crash risk — that's when the iterative version earns its keep.
98. Validate BST
The trap this problem hides: checking each node against only its immediate parent isn't enough.
5
/ \
3 8
/ \
2 9
Every parent-child pair looks fine (3 < 5, 8 > 5, 2 < 8, 9 > 8) — but 2 sits in 5's right subtree, where everything must be greater than 5. The violation comes from an ancestor two levels up, not the direct parent. So each node needs a range carved out by every ancestor, not just one.
Way 1 — Range, recursive
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def valid(node, low, high):
if not node:
return True
if not (low < node.val < high):
return False
return (valid(node.left, low, node.val) and
valid(node.right, node.val, high))
return valid(root, float('-inf'), float('inf'))Time: O(n) / Space: O(h)
Going left narrows the ceiling (high becomes my value); going right narrows the floor (low becomes my value) — each step passes down a tighter slip of paper.
Way 2 — Range, iterative
Recursive parameters become a stack tuple directly:
stack = [(root, float('-inf'), float('inf'))]
while stack:
node, low, high = stack.pop()
if not node:
continue
if not (low < node.val < high):
return False
stack.append((node.left, low, node.val))
stack.append((node.right, node.val, high))Way 3 — In-order, recursive
A different angle on the same problem: a valid BST's in-order walk (left, node, right) visits values in strictly increasing order. So instead of tracking a range, just remember the last value seen and compare.
def isValidBST(self, root):
prev = None
def inorder(node):
nonlocal prev
if not node:
return True
if not inorder(node.left):
return False
if prev is not None and node.val <= prev:
return False
prev = node.val
return inorder(node.right)
return inorder(root)nonlocal is required because prev = node.val reassigns the name — mutating a list (.append) wouldn't need it, but rebinding a plain value does.
Way 4 — In-order, iterative
stack = []
node = root
prev = None
while stack or node:
while node: # dive all the way left
stack.append(node)
node = node.left
node = stack.pop() # nothing left to dive into — visit this one
if prev is not None and node.val <= prev:
return False
prev = node.val
node = node.right # then explore the right sidenode here plays a different role than in a queue/stack-of-tuples pattern — it's a cursor tracking "where to dive from next," not a self-contained unit of work. That's why it lives outside the stack: pushing node.right directly (instead of re-entering the dive) would visit that subtree's root before its own left children, breaking in-order.
Verbal follow-ups
- What if duplicates are allowed? Depends on the exact rule — I'd clarify whether they're invalid outright or allowed on one specific side, then loosen one
<to<=accordingly. - Why not just compare parent to child? The
5, 8, 2example above — the violation can come from any ancestor, not just the direct parent.
235. Lowest Common Ancestor of a BST
The path from root to p and the path from root to q share a common prefix, then split. That split point is the LCA. Walking down while both targets agree on direction is really just following the shared portion of both paths.
class Solution:
def lowestCommonAncestor(self, root, p, q):
node = root
while node:
if p.val < node.val and q.val < node.val:
node = node.left # both paths still agree: go left together
elif p.val > node.val and q.val > node.val:
node = node.right # both paths still agree: go right together
else:
return node # paths would split here — this is the LCATime: O(h) / Space: O(1)
Follow-up: general binary tree (not BST) — LC 236
No value comparisons possible — search both subtrees and combine:
def lowestCommonAncestor(self, root, p, q):
if not root or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left or rightReturning early on root == p doesn't need to check whether q is somewhere underneath — if p is an ancestor of q, p is the LCA by definition, so no further search is needed. return left or right quietly covers two situations at once: nothing found in either side (None or None), or one side's single found node bubbling all the way up because it's the ancestor of the other.
Follow-up: nodes have parent pointers
Structurally identical to Linked List Intersection — a parent pointer behaves exactly like a next pointer walking toward a shared destination.
def lowestCommonAncestor(self, p, q):
ancestors = set()
node = p
while node:
ancestors.add(node)
node = node.parent
node = q
while node not in ancestors:
node = node.parent
return nodeO(1)-space version — same two-pointer distance-equalizing trick as the linked list problem: each pointer redirects to the other's starting node once it runs out, so both travel the same total distance and meet exactly at the LCA:
a, b = p, q
while a != b:
a = a.parent if a else q
b = b.parent if b else p
return a(Checking a itself rather than a.parent matters here — it lets both pointers synchronize to None together if p and q turn out to have no common ancestor at all, instead of looping forever.)
Follow-up: what if p or q might not exist in the tree?
The general-tree version above doesn't verify existence — fix it by counting:
def lowestCommonAncestor(self, root, p, q):
self.result = None
def dfs(node):
if not node:
return 0
count = dfs(node.left) + dfs(node.right)
if node == p or node == q:
count += 1
if count == 2 and self.result is None:
self.result = node
return count
total = dfs(root)
return self.result if total == 2 else NoneSummary
| Problem | The trick |
|---|---|
| 102 Level Order | Grid BFS's snapshot-queue engine, reused on a tree |
| — zigzag / right side / average | Same skeleton, one line of collection logic changes |
| — DFS alternative | depth == len(res) marks a floor's first visitor |
| 98 Validate BST | A range handed down by every ancestor, not just the parent |
| — in-order alternative | BST validity reframed as "is this sequence strictly increasing" |
| 235 LCA (BST) | Walking down the shared prefix of two root-to-node paths |
| 236 LCA (general tree) | Search both sides, combine; an ancestor returns itself immediately |
| — parent pointers | Same distance-equalizing trick as linked list intersection |
The thread through today: reuse before you invent. Level Order didn't need a new engine, just grid BFS's engine pointed at a different neighbor shape. And the LCA-with-parent-pointers follow-up wasn't a new problem at all — it was linked list intersection, recognized in a different costume.