The workhorse of binary-tree problems. Every recursive call answers one question; the key skill is deciding what each call should return.
| Traversal | When children are processed | Typical use |
|---|---|---|
| Pre-order | After visiting the current node | Path problems, copying, serialisation |
| In-order | Between left and right subtrees | BST sorted order, kth-smallest |
| Post-order | Before visiting the current node | Height, diameter, deletion |
Two mental models for the return value:
-
Return value IS the answer — each call returns the solved sub-problem directly to the parent. Example:
maxDepthreturns the deepest path length from the current node. The root's return value is the final answer. -
Global accumulator + local return value — the return value is a local helper quantity (e.g., height) used by the parent, while the true answer is tracked in a closure variable updated at each node. Examples:
diameter(return value = depth, accumulator = best diameter seen),maxPathSum(return value = best single-branch gain, accumulator = best full path).
Confusing these two models is the most common source of wrong solutions.
Use a deque. Each wave of the loop processes one full level.
from collections import deque
queue: deque[TreeNode] = deque([root])
while queue:
for _ in range(len(queue)): # snapshot the level width
node = queue.popleft()
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)When to prefer BFS over DFS:
- You need level-by-level information (level order, right side view).
- The tree may be deeply skewed and recursion depth is a concern.
- Shortest-path / minimum-depth questions.
In a valid BST every node satisfies:
all values in left subtree < node.val < all values in right subtree.
This lets you binary-search the tree in O(h) instead of O(n):
if target < node.val: go left
if target > node.val: go right
else: found itUsed in: LCA of BST (235), Validate BST (98), Kth Smallest (230).
| Pattern | ML connection |
|---|---|
| Max depth | max_depth hyperparameter in sklearn DecisionTreeClassifier |
| Same tree | Comparing two computation graphs for structural equality |
| Invert / transform | Reflecting a feature hierarchy or reversing pipeline DAGs |
| Diameter | Span between the two most distant leaves in a decision tree |
| Balanced check | Verifying balanced branching in ensemble trees |
| Subtree match | Sub-graph pattern search in neural-net computation graphs |
| BST LCA | Routing inference queries through split conditions |
| Symmetric | Encoder–decoder symmetry validation (U-Net, autoencoders) |
| Path sum | Decision-tree leaf condition: does this root-to-leaf path meet a threshold? |
| Merge trees | Ensemble model fusion — summing aligned leaf outputs |
| # | Problem | Traversal / Technique | Time | Space |
|---|---|---|---|---|
| 104 | Maximum Depth of Binary Tree | Post-order DFS / BFS | O(n) | O(h) |
| 100 | Same Tree | Pre-order DFS (paired) | O(n) | O(h) |
| 226 | Invert Binary Tree | Pre-order DFS (swap) | O(n) | O(h) |
| 543 | Diameter of Binary Tree | Post-order DFS + global accumulator | O(n) | O(h) |
| 110 | Balanced Binary Tree | Post-order DFS + sentinel | O(n) | O(h) |
| 572 | Subtree of Another Tree | DFS outer + DFS same-tree inner | O(n·m) | O(h) |
| 235 | LCA of Binary Search Tree | BST ordering property | O(h) | O(1) |
| 101 | Symmetric Tree | DFS mirror-pair / BFS mirror-pair | O(n) | O(h) |
| 112 | Path Sum | Pre-order DFS (target reduction) | O(n) | O(h) |
| 617 | Merge Two Binary Trees | Post-order DFS (simultaneous) | O(n) | O(h) |
| # | Problem | Traversal / Technique | Time | Space |
|---|---|---|---|---|
| 102 | Binary Tree Level Order Traversal | BFS level-by-level with width snapshot | O(n) | O(n) |
| 199 | Binary Tree Right Side View | BFS; last node per level | O(n) | O(n) |
| 1448 | Count Good Nodes in Binary Tree | DFS tracking max-so-far on path | O(n) | O(h) |
| 98 | Validate Binary Search Tree | DFS with inherited bounds [low, high] | O(n) | O(h) |
| 230 | Kth Smallest Element in a BST | Iterative in-order with early stop | O(h+k) | O(h) |
| 105 | Construct Tree from Preorder + Inorder | Divide & conquer + index map | O(n) | O(n) |
| 106 | Construct Tree from Inorder + Postorder | Divide & conquer + index map (right-first) | O(n) | O(n) |
| 1372 | Longest ZigZag Path in a Binary Tree | DFS returning (left_len, right_len) | O(n) | O(h) |
| 437 | Path Sum III | Prefix-sum hash map on DFS path + backtrack | O(n) | O(n) |
| 236 | Lowest Common Ancestor of a Binary Tree | Post-order DFS (no BST property) | O(n) | O(h) |
| 116 | Populating Next Right Pointers in Each Node | Level-link O(1) space / BFS | O(n) | O(1) |
| 114 | Flatten Binary Tree to Linked List | Reverse post-order DFS / predecessor trick | O(n) | O(h) |
| # | Problem | Key idea |
|---|---|---|
| 124 | Binary Tree Maximum Path Sum | Post-order DFS; global accumulator (the canonical hard example of the pattern) |
| 297 | Serialize and Deserialize Binary Tree | Pre-order DFS or BFS with null markers |
| 968 | Binary Tree Cameras | Greedy post-order; assign cameras from leaves up |