Tree Traversal Target: 15s
Top-down pushes state down. Bottom-up bubbles results up. Many tree problems become trivial once you pick the right direction.
TOP-DOWN vs BOTTOM-UP DFS
─────────────────────────
TOP-DOWN: pass info FROM root TO leaves
def dfs(node, info_from_parent):
# use info_from_parent
dfs(node.left, updated_info)
dfs(node.right, updated_info)
Examples:
Path sum: pass remaining sum down
Max depth: pass current depth down
Same tree: pass corresponding nodes
BOTTOM-UP: gather info FROM leaves TO root
def dfs(node):
left_info = dfs(node.left)
right_info = dfs(node.right)
return combine(left_info, right_info, node)
Examples:
Height: return 1 + max(left_h, right_h)
Diameter: return max depth, update global diameter
Balanced: return height, check balance
DECISION:
"Does parent need to tell children something?" → top-down
"Does parent need results from children?" → bottom-up
Some problems need BOTH (e.g., max path sum)Type it from memory. Go.