Recap — Tree Traversal Patterns

# Tree Traversal Patterns Binary trees appear in 25%+ of interview questions. Knowing the four traversals cold makes most tree problems mechanical. ## The tree node ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right ``` Standard LeetCode definition. ## DFS (Depth-First Search) — recursion DFS goes deep first. Three flavors based on WHEN you process the current node: ### Pre-order (root → left → right) ```python def preorder(node, result): if not node: return result.append(node.val) # process FIRST preorder(node.left, result) preorder(node.right, result) ``` Use for: copying a tree, serializing, "process before children". ### In-order (left → root → right) ```python def inorder(node, result): if not node: return inorder(node.left, result) result.append(node.val) # process IN THE MIDDLE inorder(node.right, result) ``` Use for: BST sorted traversal (gives values in increasing order!). ### Post-order (left → right → root) ```python def postorder(node, result): if not node: return postorder(node.left, result) postorder(node.right, result) result.append(node.val) # process LAST ``` Use for: deleting a tree, computing aggregates from children up (size, height, sum). ## BFS (Breadth-First Search) — level by level ```python from collections import deque def level_order(root): if not root: return [] result = [] q = deque([root]) while q: level = [] for _ in range(len(q)): # process all at current level node = q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) result.append(level) return result ``` Use for: level-order traversal, shortest path in tree, "find the X-th level", views (right side view, etc.). ## The four-traversal cheat sheet | Traversal | Order | When to use | |---|---|---| | Pre-order | Root, Left, Right | Copy tree, serialize, before-children | | In-order | Left, Root, Right | BST sorted order, validate BST | | Post-order | Left, Right, Root | Aggregate from children (size, height) | | Level-order | Top-down by depth | Level-based questions, shortest path | ## The "process from children up" pattern For most tree aggregation problems, post-order DFS is the workhorse: ```python def max_depth(node): if not node: return 0 return 1 + max(max_depth(node.left), max_depth(node.right)) def count_nodes(node): if not node: return 0 return 1 + count_nodes(node.left) + count_nodes(node.right) def diameter(node): best = [0] def height(n): if not n: return 0 l = height(n.left) r = height(n.right) best[0] = max(best[0], l + r) # diameter through this node return 1 + max(l, r) height(node) return best[0] ``` Note: `diameter` uses a nonlocal `best` because the answer might pass through any node, not just root. ## The "construct from traversals" pattern If given pre-order + in-order (or post-order + in-order), you can reconstruct a unique tree. ```python def build_tree(preorder, inorder): if not preorder: return None root = TreeNode(preorder[0]) idx = inorder.index(preorder[0]) root.left = build_tree(preorder[1:1+idx], inorder[:idx]) root.right = build_tree(preorder[1+idx:], inorder[idx+1:]) return root ``` Common interview problem; know the pattern. ## Recursion vs iteration for tree traversal Recursion is natural. Iteration with a stack works too: ```python def iterative_preorder(root): if not root: return [] result, stack = [], [root] while stack: node = stack.pop() result.append(node.val) if node.right: stack.append(node.right) # right first → left popped first if node.left: stack.append(node.left) return result ``` Use iteration when: - Stack depth is a concern (very deep tree). - Interviewer asks for iterative. ## Common tree problems and which traversal they want - **Max depth / count nodes** → post-order (aggregate) - **Inorder sequence / validate BST** → in-order - **Serialize a tree** → pre-order - **Level-order or right-side view** → BFS - **LCA (Lowest Common Ancestor)** → post-order (return found-flags up) - **Path sum** → pre-order (carry sum down) or post-order (build path up) ## Common tree-traversal mistakes 1. **Forgetting the null check.** `if not node: return` is the base case. 2. **Modifying tree during traversal.** Causes weird bugs; copy or use parent pointers. 3. **BFS with a list (not deque).** O(N²) instead of O(N). 4. **Confusing in-order with pre-order.** In-order is for BSTs. 5. **Forgetting to return a value vs append to result.** Pick one style; don't mix. ## Takeaway Four traversals: pre-order, in-order, post-order (DFS variants) and level-order (BFS). Each fits specific problem types.