Tree Traversal Fundamentals
Binary tree problems appear in nearly every technical interview. The foundation is traversal order, which determines which problems you can solve recursively versus iteratively.
- Inorder (Left → Root → Right): produces sorted output for a BST. Used for BST validation, kth-smallest, BST iterator, and converting BST to sorted array.
- Preorder (Root → Left → Right): root processed before children. Used for tree serialization, path sum problems, and building a copy of the tree.
- Postorder (Left → Right → Root): children processed before root. Used when you need information from subtrees to compute the root’s answer — subtree sums, tree height, balanced tree check, delete nodes.
- Level-order (BFS): process level by level using a queue. Used for right side view, zigzag traversal, max level sum, and populating next right pointers.
The DFS Recursive Template
Most tree problems fit one of two DFS patterns:
Pattern 1 — Return value from subtree (bottom-up): the recursive function computes something for each subtree and returns it to the parent. Use this when each node’s answer depends on its children’s answers.
def solve(node):
if not node:
return base_case
left = solve(node.left)
right = solve(node.right)
return combine(left, right, node.val)
Examples: tree height (return 1 + max(left, right)), diameter of binary tree (update global max with left+right, return 1+max(left,right)), check balanced tree.
Pattern 2 — Pass state down (top-down): pass accumulated information from parent to children. Use when each node needs context from its ancestors.
def solve(node, state):
if not node:
return
# use node.val and state
solve(node.left, new_state)
solve(node.right, new_state)
Examples: path sum (pass remaining target down), all root-to-leaf paths (pass current path), max path sum to leaf.
Classic Problems by Pattern
Height / Depth (postorder, return value): maximum depth is the canonical example. Minimum depth requires handling the case where a node has only one child — a node with one child is NOT a leaf, so minimum depth = 1 + min of the non-null child.
Diameter of Binary Tree: the diameter is the longest path between any two nodes, which may or may not pass through the root. At each node, the longest path through that node = height(left) + height(right). Track a global maximum. Return 1 + max(height(left), height(right)) for the parent. Time O(n).
Balanced Binary Tree: a tree is balanced if, for every node, |height(left) – height(right)| ≤ 1. Combine height computation and balance check in one DFS: return -1 to propagate “unbalanced” upward (early termination), else return the actual height. Time O(n) versus the naive O(n log n) solution that calls height separately.
Lowest Common Ancestor (LCA): if both target nodes are in the left subtree, recurse left. If both are in right, recurse right. If they’re on different sides (or one is the current node), the current node is the LCA. Base case: null returns null; finding either target returns the target itself. Time O(n).
Serialize and Deserialize Binary Tree: preorder traversal with null markers. Serialize: if null, append “#”; else append val and recurse left then right. Deserialize: use a queue of tokens; dequeue one token — if “#”, return null; else create a node and set left = deserialize(), right = deserialize(). Time and space O(n).
BST-Specific Problems
BST invariant: left subtree values < root < right subtree values. Inorder traversal of a BST is always sorted.
Validate BST: pass a (min, max) range down the tree. At each node, check min < node.val < max. For the left child, the new max becomes node.val. For the right child, the new min becomes node.val. Initialize with (-∞, +∞). A common mistake: comparing only parent-child relationships (misses the constraint that ALL left subtree values must be less than root).
Kth Smallest in BST: inorder traversal is sorted ascending. Use a counter; decrement on each inorder visit; when counter reaches 0, record the current node. For frequent queries with insert/delete operations, augment the BST with a subtree_count at each node to enable O(log n) kth-smallest queries.
Convert Sorted Array to BST: always pick the middle element as root (ensures height-balanced). Recurse on left half for left subtree, right half for right subtree. Time O(n).
Level-Order (BFS) Problems
BFS uses a deque. Template:
from collections import deque
queue = deque([root])
while queue:
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
# process node
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
Right Side View: the last node processed in each level is the right-side visible node. Zigzag Traversal: alternate appending left-to-right and right-to-left — use a direction flag and a deque (appendleft vs append). Max Level Sum: track max sum across levels during BFS. Populating Next Right Pointers: O(1) space BFS using the already-assigned next pointers of the previous level as the queue — process level N using next pointers to traverse level N, and set next pointers for level N+1.
Iterative Traversal
Interviewers sometimes ask for iterative implementations to avoid stack overflow on deep trees:
Iterative inorder: maintain an explicit stack. Push all left children until hitting null. Pop a node, visit it, then push its right child. Repeat.
Iterative preorder: push root; while stack not empty: pop and visit, then push right, then push left (left is processed first since stack is LIFO).
Morris traversal: O(1) space inorder using threaded tree pointers — finds the inorder predecessor of each node and threads it. Avoids both recursion stack and explicit stack. Complex to implement but shows deep tree understanding in interviews.
Interview Tips
- Null check is your base case — always ask yourself what should be returned for a null node before writing recursive code.
- Identify if you need top-down (pass info down) or bottom-up (aggregate from children) — this determines parameter vs return value.
- Global variable trick: for problems where the answer spans the root (diameter, max path sum), use a nonlocal variable updated during the bottom-up DFS while the function returns a different value to the parent.
- When asked for iterative: translate the recursion stack to an explicit stack, pushing nodes in reverse visit order.
- BST problems: always think about whether the inorder property (sorted order) can be exploited.