Intermediate · Module 13 · Lesson 2
DFS traversals
Preorder, inorder, and postorder recursive contracts.
Lesson 71 of 123
1d streakDepth-First Search (DFS): Preorder, Inorder & Postorder
DFS traverses as deep as possible along each branch before backtracking. The three classic depth-first traversals differ solely by when the current root node is visited relative to its children.
[ 1 ]
/ \
[ 2 ] [ 3 ]
/ \
[ 4 ] [ 5 ]
1. PREORDER (Root -> Left -> Right):
Order: 1 -> 2 -> 4 -> 5 -> 3
Use: Cloning a tree, serializing/deserializing, prefix expression evaluation.
2. INORDER (Left -> Root -> Right):
Order: 4 -> 2 -> 5 -> 1 -> 3
Use: In a Binary Search Tree (BST), Inorder visits nodes in strictly SORTED ASCENDING order!
3. POSTORDER (Left -> Right -> Root):
Order: 4 -> 5 -> 2 -> 3 -> 1
Use: Deleting a tree safely (children freed before parent), calculating subtree heights, bottom-up DP.| Traversal | Order Formula | Primary Interview Use Case | BST Property |
|---|---|---|---|
| Preorder | Root → Left → Right | Tree serialization, deep copy, prefix syntax | Root appears first |
| Inorder | Left → Root → Right | Validating BST, finding k-th smallest element | Produces sorted order |
| Postorder | Left → Right → Root | Bottom-up height calculation, tree deletion, LCA | Leaves evaluated first |
// 1. Recursive Inorder Traversal: O(n) time, O(h) auxiliary stack space
public void inorder(TreeNode root, List<Integer> result) {
if (root == null) return;
inorder(root.left, result); // 1. Traverse left subtree
result.add(root.val); // 2. Visit root
inorder(root.right, result); // 3. Traverse right subtree
}
// 2. Iterative Inorder Traversal using an Explicit Stack (Eliminates recursion)
public List<Integer> inorderIterative(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
// Step 1: Push all left children until hitting null
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
// Step 2: Node at top has no unvisited left children -> Visit it!
curr = stack.pop();
result.add(curr.val);
// Step 3: Shift to right subtree
curr = curr.right;
}
return result;
}Active Recall Checkpoint
Given a Binary Search Tree, which traversal produces a strictly monotonically increasing list of values?
Hint: Think about where the left (smaller) and right (larger) nodes sit relative to the root.
Show answer & explanation
Inorder traversal (Left -> Root -> Right). In a BST, all left descendants are smaller than the root, and all right descendants are larger. Visiting Left first, then Root, then Right yields sorted ascending order.
Cost Model
Complexity & Trade-offs
When to use it
- Hierarchies, ordered sets/maps, expression trees, and recursive aggregation.
- Path, ancestor, depth, and subtree questions.
- Maintaining sorted dynamic data with balanced trees.
Common mistakes
- Assuming a BST is balanced without a balancing guarantee.
- Confusing node depth with subtree height.
- Discarding information needed by the parent instead of returning it.
Practice prompts
- Reproduce the worked DFS traversals example without looking at the trace.
- Change one input condition and explain whether the DFS traversals invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check