Tree Depth-First Search — How the Pattern Works
Tree Depth-First Search (DFS) explores each root-to-leaf branch to completion before backtracking, using the call stack to pass ancestor state top-down via parameters and aggregate subtree properties bottom-up via return values. At every node u, the recursion maintains the invariant that parameters summarize the exact root-to-u path context while child return values represent fully solved properties of u.left and u.right. By evaluating subtree metrics once in postorder, propagating ancestor bounds in preorder, or combining both in a two-pass rerooting traversal, DFS eliminates redundant subtree scans and reduces O(n^2) recomputation to O(n) time (or O(h) along a guided BST path) with O(h) stack space.
- Optimizing or aggregating over subtrees and paths that may bend at any node (
Diameter of Binary Tree,Binary Tree Maximum Path Sum,Lowest Common Ancestor), where each node combines independent bottom-up answers fromnode.leftandnode.rightin postorder. - Enforcing or querying path-dependent constraints from the root (
Validate Binary Search Tree,Path Sum,Binary Tree Right Side View), where ancestor bounds, depths, or remaining target budgets flow top-down. - Querying ordered keys, ranks, or nearest neighbors in a Binary Search Tree (
Inorder Successor in BST,Closest Binary Search Tree Value,Kth Smallest Element in a BST), leveraging BST ordering for an O(h) root-to-leaf walk or early-stopping inorder traversal. - Serializing, reconstructing, or rewiring tree topology (
Flatten Binary Tree to Linked List,Serialize and Deserialize Binary Tree,Build Binary Tree from Preorder and Inorder Traversal), where traversal order uniquely determines pointer links. - Computing answers for every node or under virtual subtree removals (
Sum of Distances in a Tree,Height of Binary Tree After Subtree Removal Queries), pairing a bottom-up subtree pass with a top-down complement or rerooting pass.
- Mixing up node-count height and edge-count height: returning
0forNoneassigns leaves height1(nodes on downward path), whereas returning-1forNoneassigns leaves height0(edges on downward path, required when summingdepth + heightinSubtree Removal Queries). - Returning a forked two-sided path to a parent in bending-path problems (
Diameter of Binary Tree,Binary Tree Maximum Path Sum):left + node + rightis valid only as a candidate peaking atnode, whereas the recursive return value tonode's parent must extend at most one branch. - Validating only immediate parent-child pairs in
Validate Binary Search Treeor acceptingremaining == 0at internal nodes inPath Sum: ancestor bounds(low, high)must propagate across all levels, and root-to-leaf checks requirenot node.left and not node.right. - Initializing global maxima to
0instead offloat('-inf')when node values can be negative (Binary Tree Maximum Path Sum), which erroneously prefers an empty path over the least-negative node.
def postorder_aggregate(root):
best = 0
def dfs(node):
nonlocal best
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
best = max(best, left + right)
return 1 + max(left, right)
dfs(root)
return bestdef preorder_validate(root):
def dfs(node, low, high):
if not node:
return True
if not (low < node.val < high):
return False
return (dfs(node.left, low, node.val) and
dfs(node.right, node.val, high))
return dfs(root, float("-inf"), float("inf"))def bst_guided_walk(root, target):
candidate = None
node = root
while node:
if node.val > target:
candidate = node
node = node.left
else:
node = node.right
return candidatedef inorder_early_stop(root, k):
count, ans = 0, None
def dfs(node):
nonlocal count, ans
if not node or ans is not None:
return
dfs(node.left)
count += 1
ans = node.val if count == k else ans
dfs(node.right)
dfs(root)
return ans