Binary Tree DFS Traversals
What Is DFS Traversal?
Depth-First Search (DFS) explores a tree by going as deep as possible along each branch before backtracking. On a binary tree, DFS visits nodes by following one branch all the way to a leaf, then backing up and trying the next branch.
There are exactly three DFS traversal orders — determined by when the current node is visited relative to its left and right subtrees:
Reference tree for all examples:
1
/ \
2 3
/ \ / \
4 5 6 7
PREORDER (Root → Left → Right): 1, 2, 4, 5, 3, 6, 7
Visit node, then recurse left, then recurse right.
INORDER (Left → Root → Right): 4, 2, 5, 1, 6, 3, 7
Recurse left, visit node, then recurse right.
POSTORDER (Left → Right → Root): 4, 5, 2, 6, 7, 3, 1
Recurse left, recurse right, then visit node.
Traversal 1: Preorder (Root → Left → Right)
Visit the current node before its children. The root is always the first node visited.
Preorder on: 1
/ \
2 3
/ \ / \
4 5 6 7
Step-by-step:
Visit 1 → output: [1]
Go left → Visit 2 → output: [1, 2]
Go left → Visit 4 → output: [1, 2, 4]
4 has no children → backtrack to 2
Go right → Visit 5 → output: [1, 2, 4, 5]
5 has no children → backtrack to 1
Go right → Visit 3 → output: [1, 2, 4, 5, 3]
Go left → Visit 6 → output: [1, 2, 4, 5, 3, 6]
6 has no children → backtrack to 3
Go right → Visit 7 → output: [1, 2, 4, 5, 3, 6, 7]
Result: [1, 2, 4, 5, 3, 6, 7]
When to use: Copying a tree (preorder gives the insertion order to reconstruct it), serializing a tree, printing directory structure (parent before children).
Recursive Preorder
1import java.util.*;
2
3public class PreorderTraversal {
4
5 static class TreeNode {
6 int val; TreeNode left, right;
7 TreeNode(int v) { val = v; }
8 }
9
10 // Recursive preorder
11 public static List<Integer> preorderRecursive(TreeNode root) {
12 List<Integer> result = new ArrayList<>();
13 preorder(root, result);
14 return result;
15 }
16
17 private static void preorder(TreeNode node, List<Integer> result) {
18 if (node == null) return; // Base case
19
20 result.add(node.val); // 1. Visit ROOT
21 preorder(node.left, result); // 2. Recurse LEFT
22 preorder(node.right, result); // 3. Recurse RIGHT
23 }
24
25 // Iterative preorder using a stack
26 public static List<Integer> preorderIterative(TreeNode root) {
27 List<Integer> result = new ArrayList<>();
28 if (root == null) return result;
29
30 Deque<TreeNode> stack = new ArrayDeque<>();
31 stack.push(root);
32
33 while (!stack.isEmpty()) {
34 TreeNode node = stack.pop();
35 result.add(node.val); // Visit node
36
37 // Push RIGHT first, LEFT second — so LEFT is popped first (LIFO)
38 if (node.right != null) stack.push(node.right);
39 if (node.left != null) stack.push(node.left);
40 }
41
42 return result;
43 }
44
45 public static void main(String[] args) {
46 TreeNode root = new TreeNode(1);
47 root.left = new TreeNode(2); root.right = new TreeNode(3);
48 root.left.left = new TreeNode(4); root.left.right = new TreeNode(5);
49 root.right.left = new TreeNode(6); root.right.right = new TreeNode(7);
50
51 System.out.println(preorderRecursive(root)); // [1, 2, 4, 5, 3, 6, 7]
52 System.out.println(preorderIterative(root)); // [1, 2, 4, 5, 3, 6, 7]
53 }
54}Output:
[1, 2, 4, 5, 3, 6, 7]
[1, 2, 4, 5, 3, 6, 7]
Traversal 2: Inorder (Left → Root → Right)
Visit the current node between its left and right subtrees. For a BST, this always produces elements in sorted ascending order.
Inorder on: 1
/ \
2 3
/ \ / \
4 5 6 7
Step-by-step:
Go left all the way → reach 4 (leftmost)
Visit 4 → output: [4]
Backtrack to 2, visit 2 → output: [4, 2]
Go right to 5, visit 5 → output: [4, 2, 5]
Backtrack to 1, visit 1 → output: [4, 2, 5, 1]
Go right to 3, go left to 6, visit 6 → output: [4, 2, 5, 1, 6]
Backtrack to 3, visit 3 → output: [4, 2, 5, 1, 6, 3]
Go right to 7, visit 7 → output: [4, 2, 5, 1, 6, 3, 7]
Result: [4, 2, 5, 1, 6, 3, 7]
When to use: Validating a BST (check if inorder is sorted), finding kth smallest in BST, converting BST to sorted array, flattening a tree to a sorted list.
Recursive and Iterative Inorder
1import java.util.*;
2
3public class InorderTraversal {
4
5 static class TreeNode {
6 int val; TreeNode left, right;
7 TreeNode(int v) { val = v; }
8 }
9
10 // Recursive inorder
11 public static List<Integer> inorderRecursive(TreeNode root) {
12 List<Integer> result = new ArrayList<>();
13 inorder(root, result);
14 return result;
15 }
16
17 private static void inorder(TreeNode node, List<Integer> result) {
18 if (node == null) return;
19
20 inorder(node.left, result); // 1. Recurse LEFT
21 result.add(node.val); // 2. Visit ROOT
22 inorder(node.right, result); // 3. Recurse RIGHT
23 }
24
25 // Iterative inorder — explicit stack + current pointer
26 public static List<Integer> inorderIterative(TreeNode root) {
27 List<Integer> result = new ArrayList<>();
28 Deque<TreeNode> stack = new ArrayDeque<>();
29 TreeNode curr = root;
30
31 while (curr != null || !stack.isEmpty()) {
32 // Push all left children onto stack (go as deep left as possible)
33 while (curr != null) {
34 stack.push(curr);
35 curr = curr.left;
36 }
37
38 // Pop from stack — this is the leftmost unvisited node
39 curr = stack.pop();
40 result.add(curr.val); // Visit node
41
42 // Move to right subtree
43 curr = curr.right;
44 }
45
46 return result;
47 }
48
49 public static void main(String[] args) {
50 TreeNode root = new TreeNode(1);
51 root.left = new TreeNode(2); root.right = new TreeNode(3);
52 root.left.left = new TreeNode(4); root.left.right = new TreeNode(5);
53 root.right.left = new TreeNode(6); root.right.right = new TreeNode(7);
54
55 System.out.println(inorderRecursive(root)); // [4, 2, 5, 1, 6, 3, 7]
56 System.out.println(inorderIterative(root)); // [4, 2, 5, 1, 6, 3, 7]
57 }
58}Output:
[4, 2, 5, 1, 6, 3, 7]
[4, 2, 5, 1, 6, 3, 7]
Dry Run: Iterative Inorder Stack Trace
Tree: 1
/ \
2 3
/ \
4 5
curr=1, stack=[]
Iteration 1 — push all left:
Push 1: stack=[1], curr=2
Push 2: stack=[1,2], curr=4
Push 4: stack=[1,2,4], curr=null
Pop 4: visit 4, result=[4], curr=4.right=null
Iteration 2 — push all left (none):
curr=null, pop 2: visit 2, result=[4,2], curr=2.right=5
Iteration 3 — push all left:
Push 5: stack=[1,5], curr=null
Pop 5: visit 5, result=[4,2,5], curr=5.right=null
Iteration 4 — push all left (none):
curr=null, pop 1: visit 1, result=[4,2,5,1], curr=1.right=3
Iteration 5 — push all left:
Push 3: stack=[3], curr=null
Pop 3: visit 3, result=[4,2,5,1,3]
(no right subtrees in this simplified tree)
Traversal 3: Postorder (Left → Right → Root)
Visit the current node after both its subtrees. The root is always the last node visited.
Postorder on: 1
/ \
2 3
/ \ / \
4 5 6 7
Step-by-step:
Go deep left → reach 4
4 has no children → Visit 4 → output: [4]
Backtrack to 2, go right → reach 5
5 has no children → Visit 5 → output: [4, 5]
Both children of 2 done → Visit 2 → output: [4, 5, 2]
Backtrack to 1, go right → reach 3, go left → reach 6
6 has no children → Visit 6 → output: [4, 5, 2, 6]
Backtrack to 3, go right → reach 7
7 has no children → Visit 7 → output: [4, 5, 2, 6, 7]
Both children of 3 done → Visit 3 → output: [4, 5, 2, 6, 7, 3]
Both children of 1 done → Visit 1 → output: [4, 5, 2, 6, 7, 3, 1]
Result: [4, 5, 2, 6, 7, 3, 1]
When to use: Deleting a tree (delete children before parent), computing sizes/heights (need child values first), evaluating expression trees (evaluate operands before operator).
Recursive and Iterative Postorder
1import java.util.*;
2
3public class PostorderTraversal {
4
5 static class TreeNode {
6 int val; TreeNode left, right;
7 TreeNode(int v) { val = v; }
8 }
9
10 // Recursive postorder
11 public static List<Integer> postorderRecursive(TreeNode root) {
12 List<Integer> result = new ArrayList<>();
13 postorder(root, result);
14 return result;
15 }
16
17 private static void postorder(TreeNode node, List<Integer> result) {
18 if (node == null) return;
19
20 postorder(node.left, result); // 1. Recurse LEFT
21 postorder(node.right, result); // 2. Recurse RIGHT
22 result.add(node.val); // 3. Visit ROOT
23 }
24
25 // Iterative postorder — two-stack approach
26 public static List<Integer> postorderIterative(TreeNode root) {
27 List<Integer> result = new ArrayList<>();
28 if (root == null) return result;
29
30 Deque<TreeNode> stack1 = new ArrayDeque<>(); // Processing stack
31 Deque<TreeNode> stack2 = new ArrayDeque<>(); // Result stack
32
33 stack1.push(root);
34
35 while (!stack1.isEmpty()) {
36 TreeNode node = stack1.pop();
37 stack2.push(node); // Push to result stack (reversed order)
38
39 // Push LEFT then RIGHT to stack1 — so RIGHT is processed first
40 if (node.left != null) stack1.push(node.left);
41 if (node.right != null) stack1.push(node.right);
42 }
43
44 // Drain result stack — gives postorder
45 while (!stack2.isEmpty()) {
46 result.add(stack2.pop().val);
47 }
48 return result;
49 }
50
51 // Iterative postorder — one-stack approach
52 public static List<Integer> postorderOneStack(TreeNode root) {
53 LinkedList<Integer> result = new LinkedList<>();
54 if (root == null) return result;
55
56 Deque<TreeNode> stack = new ArrayDeque<>();
57 stack.push(root);
58
59 while (!stack.isEmpty()) {
60 TreeNode node = stack.pop();
61 result.addFirst(node.val); // Add to FRONT — reverses to postorder
62
63 if (node.left != null) stack.push(node.left);
64 if (node.right != null) stack.push(node.right);
65 }
66 return result;
67 }
68
69 public static void main(String[] args) {
70 TreeNode root = new TreeNode(1);
71 root.left = new TreeNode(2); root.right = new TreeNode(3);
72 root.left.left = new TreeNode(4); root.left.right = new TreeNode(5);
73 root.right.left = new TreeNode(6); root.right.right = new TreeNode(7);
74
75 System.out.println(postorderRecursive(root)); // [4, 5, 2, 6, 7, 3, 1]
76 System.out.println(postorderIterative(root)); // [4, 5, 2, 6, 7, 3, 1]
77 System.out.println(postorderOneStack(root)); // [4, 5, 2, 6, 7, 3, 1]
78 }
79}Output:
[4, 5, 2, 6, 7, 3, 1]
[4, 5, 2, 6, 7, 3, 1]
Morris Traversal — O(1) Space Inorder
Standard inorder traversal uses O(h) space (h = height) for the recursion stack or explicit stack. Morris Traversal achieves the same inorder result using O(1) extra space by temporarily modifying the tree — threading right pointers to link each node back to its inorder successor.
IDEA:
For each node curr, find its INORDER PREDECESSOR
(the rightmost node in curr's left subtree).
Temporarily set predecessor.right = curr (a "thread").
This thread lets us return to curr without a stack.
When we arrive at curr a second time (via the thread):
the thread means curr's left subtree is fully processed.
Remove the thread and visit curr.
VISUAL — threading step by step on:
4
/ \
2 5
/ \
1 3
Step 1: curr=4. Left exists.
Predecessor of 4 = rightmost in left subtree = 3
3.right = null → CREATE THREAD: 3.right = 4
Move curr to curr.left = 2
4 ←──────────┐ (thread)
/ \ │
2 5 │
/ \ │
1 3──────────────┘
Step 2: curr=2. Left exists.
Predecessor of 2 = 1 (rightmost in 2's left subtree)
1.right = null → CREATE THREAD: 1.right = 2
Move curr = 1
Step 3: curr=1. No left child.
VISIT 1 → output: [1]
Move curr = 1.right = 2 (via thread)
Step 4: curr=2. Left exists.
Predecessor of 2 = 1 → 1.right = 2 (thread exists!)
THREAD EXISTS → VISIT 2 → output: [1, 2]
REMOVE THREAD: 1.right = null
Move curr = 2.right = 3
Step 5: curr=3. No left child.
VISIT 3 → output: [1, 2, 3]
Move curr = 3.right = 4 (via thread)
Step 6: curr=4. Left exists.
Predecessor of 4 = 3 → 3.right = 4 (thread exists!)
THREAD EXISTS → VISIT 4 → output: [1, 2, 3, 4]
REMOVE THREAD: 3.right = null
Move curr = 4.right = 5
Step 7: curr=5. No left child.
VISIT 5 → output: [1, 2, 3, 4, 5]
Move curr = null → DONE
Result: [1, 2, 3, 4, 5] ✓ — correct inorder, O(1) space
1import java.util.*;
2
3public class MorrisInorder {
4
5 static class TreeNode {
6 int val; TreeNode left, right;
7 TreeNode(int v) { val = v; }
8 }
9
10 public static List<Integer> morrisInorder(TreeNode root) {
11 List<Integer> result = new ArrayList<>();
12 TreeNode curr = root;
13
14 while (curr != null) {
15 if (curr.left == null) {
16 // No left subtree — visit curr and move right
17 result.add(curr.val);
18 curr = curr.right;
19 } else {
20 // Find inorder predecessor (rightmost in left subtree)
21 TreeNode pred = curr.left;
22 while (pred.right != null && pred.right != curr) {
23 pred = pred.right;
24 }
25
26 if (pred.right == null) {
27 // First visit: create thread, move left
28 pred.right = curr; // Create thread
29 curr = curr.left;
30 } else {
31 // Second visit: thread exists — left done
32 pred.right = null; // Remove thread (restore tree)
33 result.add(curr.val);
34 curr = curr.right;
35 }
36 }
37 }
38
39 return result;
40 }
41
42 public static void main(String[] args) {
43 TreeNode root = new TreeNode(4);
44 root.left = new TreeNode(2); root.right = new TreeNode(5);
45 root.left.left = new TreeNode(1); root.left.right = new TreeNode(3);
46
47 System.out.println(morrisInorder(root)); // [1, 2, 3, 4, 5]
48 }
49}Output:
[1, 2, 3, 4, 5]
Choosing the Right Traversal
TRAVERSAL ORDER WHEN TO USE
─────────────────────────────────────────────────────────────────────
Preorder Root→Left→Right Copy/serialize a tree
Print directory structure
Reconstruct tree from preorder+inorder
Prefix expression evaluation
Inorder Left→Root→Right BST → sorted sequence
Validate BST (check sorted order)
kth smallest in BST
Binary expression trees (infix)
Postorder Left→Right→Root Delete a tree (children before parent)
Compute tree height/size (bottom-up)
Evaluate expression trees (postfix)
Directory size (sum up children first)
Complexity Summary
| Traversal | Recursive Time | Recursive Space | Iterative Space | Morris Space |
|---|---|---|---|---|
| Preorder | O(n) | O(h) | O(h) | O(1)* |
| Inorder | O(n) | O(h) | O(h) | O(1) |
| Postorder | O(n) | O(h) | O(h) | O(1)* |
h = height of tree = O(log n) balanced, O(n) worst case.
* Morris preorder/postorder exist but are more complex to implement.
Common Mistakes
Wrong push order in iterative preorder. Push the RIGHT child first, then the LEFT child. Since a stack is LIFO, the left child will be popped first — maintaining Root→Left→Right order. Pushing left first causes Root→Right→Left output.
Using node.right = null condition in iterative inorder. The iterative inorder loop condition should be curr != null || !stack.isEmpty(). Stopping when only curr == null misses nodes still in the stack.
Morris traversal: not checking pred.right != curr in predecessor search. Without this check, the inner while loop runs past the thread and into an infinite cycle. The condition pred.right != null && pred.right != curr must check both — stop at a real null (go further right) OR at a thread back to curr (we have already visited left).
Confusing postorder iterative strategies. The two-stack approach and the reverse-preorder approach both give correct postorder. The key insight for reverse-preorder: preorder is Root→Left→Right; visiting Right before Left (instead) gives Root→Right→Left; reversing that gives Left→Right→Root = postorder.
Interview Questions
Q: How does inorder traversal of a BST produce sorted output?
A BST satisfies: all values in the left subtree < root < all values in right subtree, recursively. Inorder visits Left→Root→Right. This means smaller-than-root elements are visited first (all of left subtree), then the root, then larger elements (right subtree). Since this property holds at every node, the inorder traversal visits every node in strictly increasing order — producing a sorted sequence.
Q: What is the time and space complexity of DFS traversals?
All three DFS traversals (preorder, inorder, postorder) visit every node exactly once — O(n) time. Space is O(h) where h is the tree height: the recursion stack (or explicit stack) holds at most one frame per level on the current root-to-leaf path. For a balanced tree, h = O(log n); for a skewed tree, h = O(n). Morris traversal achieves O(1) extra space by using the tree structure itself (threading) instead of a stack.
Q: When would you use postorder over preorder?
Postorder is needed when a node's computation depends on its children's results — a bottom-up dependency. Classic examples: computing tree height (need children's heights first), computing subtree sizes, deleting a tree (must delete children before the parent node to avoid dangling pointers), and evaluating expression trees (operands before operator). Preorder is used when the parent's value is needed before recursing into children — copying a tree, serialization, or producing prefix expressions.
Summary
Three DFS traversal orders — differing only in when the current node is visited:
Preorder: Visit → Left → Right (Root first) Inorder: Left → Visit → Right (Root in middle) Postorder: Left → Right → Visit (Root last)
Recursive implementations are three lines each — one result.add() moved to different positions. O(n) time, O(h) space.
Iterative implementations:
- ›Preorder: stack, push right then left (LIFO gives left first)
- ›Inorder: current pointer + stack, push all left, pop, visit, move right
- ›Postorder: reverse of modified preorder (push left then right, collect, reverse)
Morris traversal achieves O(1) space inorder by threading the tree — temporarily linking each node's inorder predecessor's right pointer back to the node. After visiting, threads are removed restoring the original tree.
In the next topic you will explore Level Order Traversal (BFS) — visiting nodes level by level using a queue, zigzag traversal, right side view, and all level-based problems.
For a tree with root 1, left child 2, right child 3: what is the preorder traversal?