Tree DFS (In/Pre/Post)
The Intuition
Imagine you're exploring a cave system with a flashlight and a ball of string. At every fork, you pick one tunnel (say, the left one) and go as deep as you possibly can. You hit a dead end. You follow your string back to the last fork and try the right tunnel. Dead end again. Back up to the previous fork. Repeat until you've seen every chamber.
That's depth-first search. You commit fully to one path before trying another. The three classic orderings are just about when you write down what you see in each chamber. Preorder: you write it down the moment you walk in, before exploring any tunnels. Inorder: you explore the left tunnel, come back, write it down, then explore the right tunnel. Postorder: you explore both tunnels first, then write it down on your way out.
Why does inorder on a binary search tree give you sorted output? Because in a BST, everything in the left subtree is smaller and everything in the right is larger. Inorder visits left first, then the current node, then right. Smaller values, then current, then larger values. Sorted.
Recursion handles the backtracking for you. The call stack is your ball of string. Each recursive call goes deeper, and when it returns, you're automatically back at the fork. If you want to avoid recursion (say, for a very deep tree), you use an explicit stack and simulate the same process. The iterative version of inorder is the trickiest: you push nodes as you go left, pop to process, then go right. But the idea is identical to the cave with the string.
Serialization, expression evaluation, BST validation, tree construction from traversals, path sum problems, or any tree problem requiring recursive decomposition.
- Need shortest path in a tree (use BFS)
- Need level-order information
- Tree is extremely deep and might overflow the call stack (use iterative BFS)
Variations:
- Pre-order: Used for serialization, copying trees, prefix expressions.
- In-order: Gives sorted order for BSTs; used for BST validation.
- Post-order: Used for deletion, postfix expressions, computing subtree sizes.
- Iterative: Uses explicit stack when recursion depth is a concern.
- empty tree
- single node
- skewed tree
Key Points
- •Pre-order: process node BEFORE children (root-left-right)
- •In-order: process node BETWEEN children (left-root-right). Gives sorted order in BST
- •Post-order: process node AFTER children (left-right-root)
- •Recursive approach mirrors the traversal naturally
- •Space is O(h) where h = tree height; O(log n) balanced, O(n) worst case
Code Template
1 class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7 def preorder(root):
8 """Pre-order: root -> left -> right."""
9 if not root:
10 return []
11 return [root.val] + preorder(root.left) + preorder(root.right)
12
13 def inorder(root):
14 """In-order: left -> root -> right (sorted for BST)."""
15 if not root:
16 return []
17 return inorder(root.left) + [root.val] + inorder(root.right)
18
19 def postorder(root):
20 """Post-order: left -> right -> root."""
21 if not root:
22 return []
23 return postorder(root.left) + postorder(root.right) + [root.val]
24
25 # Iterative in-order using stack
26 def inorder_iterative(root):
27 result, stack = [], []
28 current = root
29 while current or stack:
30 while current:
31 stack.append(current)
32 current = current.left
33 current = stack.pop()
34 result.append(current.val)
35 current = current.right
36 return resultCommon Mistakes
- Confusing pre/in/post ordering for specific problems
- Not handling the null/None base case
- Forgetting that in-order on BST gives sorted output