BST DFS Traversals
Why BST Traversals Are Different
In a general binary tree, DFS traversals (preorder, inorder, postorder) are just orders to visit nodes. In a BST, the inorder traversal has a special meaning: it always visits nodes in sorted ascending order because of the BST property.
BST: 8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
Inorder (Left → Root → Right):
1 → 3 → 4 → 6 → 7 → 8 → 10 → 13 → 14
This is sorted! And it's guaranteed for ANY valid BST.
Why?
At every node: all left < node < all right
Inorder visits all of left first, then node, then all of right
= smaller values first, node in middle, larger values last
= sorted ascending ✓
This single property enables: BST validation, kth smallest, floor/ceil, conversion problems — all using traversal patterns.
Inorder Traversal — BST-Specific Value
1import java.util.*;
2
3public class BSTInorder {
4
5 static class TreeNode {
6 int val; TreeNode left, right;
7 TreeNode(int v) { val = v; }
8 }
9
10 // Recursive inorder — gives sorted output for BST
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 inorder(node.left, result); // All smaller values
20 result.add(node.val); // This node
21 inorder(node.right, result); // All larger values
22 }
23
24 // Iterative inorder — O(h) space, same sorted output
25 public static List<Integer> inorderIterative(TreeNode root) {
26 List<Integer> result = new ArrayList<>();
27 Deque<TreeNode> stack = new ArrayDeque<>();
28 TreeNode curr = root;
29
30 while (curr != null || !stack.isEmpty()) {
31 // Push all left children (go to minimum)
32 while (curr != null) {
33 stack.push(curr);
34 curr = curr.left;
35 }
36
37 // Pop minimum unvisited node
38 curr = stack.pop();
39 result.add(curr.val); // Visit in sorted order
40
41 // Move to right subtree (next larger)
42 curr = curr.right;
43 }
44
45 return result;
46 }
47
48 public static void main(String[] args) {
49 TreeNode root = new TreeNode(8);
50 root.left = new TreeNode(3); root.right = new TreeNode(10);
51 root.left.left = new TreeNode(1); root.left.right = new TreeNode(6);
52 root.right.right = new TreeNode(14);
53 root.left.right.left = new TreeNode(4);
54 root.left.right.right = new TreeNode(7);
55 root.right.right.left = new TreeNode(13);
56
57 System.out.println("Recursive: " + inorderRecursive(root));
58 // [1, 3, 4, 6, 7, 8, 10, 13, 14]
59
60 System.out.println("Iterative: " + inorderIterative(root));
61 // [1, 3, 4, 6, 7, 8, 10, 13, 14]
62 }
63}Output:
Recursive: [1, 3, 4, 6, 7, 8, 10, 13, 14]
Iterative: [1, 3, 4, 6, 7, 8, 10, 13, 14]
Application 1: Validate a BST
Use inorder traversal to check that each visited value is strictly greater than the previous — any violation means the BST property is broken.
VALID BST inorder: 1 → 3 → 4 → 6 → 7 → 8 → 10 → 13 → 14 Each value > previous ✓ INVALID BST inorder: 1 → 3 → 4 → 6 → 7 → 3 → 10 → ... 7 → 3: 3 < 7 → VIOLATION ✗ Two approaches: 1. Inorder traversal — collect values, check if sorted O(n) time, O(n) space 2. Inorder with tracking — check previous node on the fly O(n) time, O(h) space ← better 3. Range validation — pass [min, max] bounds recursively O(n) time, O(h) space ← also correct
1public class ValidateBST {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 // Approach 1: Inorder + track previous value
9 private static long prev = Long.MIN_VALUE; // Tracks last visited value
10
11 public static boolean isValidBST_Inorder(TreeNode root) {
12 prev = Long.MIN_VALUE;
13 return validate(root);
14 }
15
16 private static boolean validate(TreeNode node) {
17 if (node == null) return true;
18
19 // Check left subtree
20 if (!validate(node.left)) return false;
21
22 // Check current value is greater than previous (inorder must be strictly increasing)
23 if (node.val <= prev) return false;
24 prev = node.val;
25
26 // Check right subtree
27 return validate(node.right);
28 }
29
30 // Approach 2: Range validation (min, max bounds passed down)
31 public static boolean isValidBST_Range(TreeNode root) {
32 return checkRange(root, Long.MIN_VALUE, Long.MAX_VALUE);
33 }
34
35 private static boolean checkRange(TreeNode node, long min, long max) {
36 if (node == null) return true;
37
38 if (node.val <= min || node.val >= max) return false; // Violates range
39
40 return checkRange(node.left, min, node.val) && // Left: max = node.val
41 checkRange(node.right, node.val, max); // Right: min = node.val
42 }
43
44 public static void main(String[] args) {
45 // Valid BST: 2 / 1, 3
46 TreeNode valid = new TreeNode(2);
47 valid.left = new TreeNode(1); valid.right = new TreeNode(3);
48 System.out.println("Valid BST: " + isValidBST_Inorder(valid)); // true
49 System.out.println("Valid BST: " + isValidBST_Range(valid)); // true
50
51 // Invalid: 5 / 1, 4 / 3, 6 — 4 is in right subtree but < 5
52 TreeNode invalid = new TreeNode(5);
53 invalid.left = new TreeNode(1); invalid.right = new TreeNode(4);
54 invalid.right.left = new TreeNode(3); invalid.right.right = new TreeNode(6);
55 System.out.println("Invalid BST: " + isValidBST_Inorder(invalid)); // false
56 System.out.println("Invalid BST: " + isValidBST_Range(invalid)); // false
57 }
58}Output:
Valid inorder: true
Valid range: true
Invalid inorder: false
Invalid range: false
Application 2: Kth Smallest Element
Use inorder traversal and stop after visiting exactly k nodes. The kth visited node is the kth smallest.
BST: 3
/ \
1 4
\
2
Inorder: 1 → 2 → 3 → 4
k=1: stop at 1st node → answer = 1
k=2: stop at 2nd node → answer = 2
k=3: stop at 3rd node → answer = 3
k=4: stop at 4th node → answer = 4
1public class KthSmallest {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 // Recursive approach — uses counter array for mutable state
9 private static int[] counter = {0};
10 private static int result = -1;
11
12 public static int kthSmallest(TreeNode root, int k) {
13 counter[0] = 0; result = -1;
14 inorder(root, k);
15 return result;
16 }
17
18 private static void inorder(TreeNode node, int k) {
19 if (node == null || counter[0] >= k) return;
20
21 inorder(node.left, k); // Visit all smaller first
22
23 counter[0]++;
24 if (counter[0] == k) { // k-th visited node
25 result = node.val;
26 return;
27 }
28
29 inorder(node.right, k);
30 }
31
32 // Iterative approach — more efficient: stops immediately when found
33 public static int kthSmallestIterative(TreeNode root, int k) {
34 java.util.Deque<TreeNode> stack = new java.util.ArrayDeque<>();
35 TreeNode curr = root;
36 int count = 0;
37
38 while (curr != null || !stack.isEmpty()) {
39 while (curr != null) {
40 stack.push(curr);
41 curr = curr.left;
42 }
43
44 curr = stack.pop();
45 count++;
46
47 if (count == k) return curr.val; // Found kth smallest
48
49 curr = curr.right;
50 }
51
52 return -1; // k > number of nodes
53 }
54
55 public static void main(String[] args) {
56 // 3
57 // / \
58 // 1 4
59 // \
60 // 2
61 TreeNode root = new TreeNode(3);
62 root.left = new TreeNode(1); root.right = new TreeNode(4);
63 root.left.right = new TreeNode(2);
64
65 System.out.println("1st smallest: " + kthSmallest(root, 1)); // 1
66 System.out.println("2nd smallest: " + kthSmallest(root, 2)); // 2
67 System.out.println("3rd smallest: " + kthSmallestIterative(root, 3)); // 3
68 System.out.println("4th smallest: " + kthSmallestIterative(root, 4)); // 4
69 }
70}Output:
1st smallest: 1
2nd smallest: 2
3rd smallest: 3
4th smallest: 4
Application 3: Convert BST to Greater Sum Tree
Replace each node's value with the sum of all values greater than or equal to that node. This requires processing nodes in descending order — use reverse inorder (Right → Root → Left).
BST: 4 Greater Sum Tree:
/ \ 30
1 6 → / \
\ / \ 36 21
2 5 7 \ / \
35 26 15
Reverse inorder sequence: 7, 6, 5, 4, 2, 1
Running sum: 7, 13, 18, 22, 24, 25, 36 ... wait, let me recompute:
BST values: 1, 2, 4, 5, 6, 7
Reverse inorder visits: 7, 6, 5, 4, 2, 1
Running sum:
Visit 7: sum=7, node 7 becomes 7
Visit 6: sum=13, node 6 becomes 13
Visit 5: sum=18, node 5 becomes 18
Visit 4: sum=22, node 4 becomes 22
Visit 2: sum=24, node 2 becomes 24
Visit 1: sum=25, node 1 becomes 25
Result tree (new values): root=22, left=25/24, right=13/18/7
1public class BSTToGreaterTree {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 private static int runningSum = 0;
9
10 public static TreeNode convertBST(TreeNode root) {
11 runningSum = 0;
12 reverseInorder(root);
13 return root;
14 }
15
16 // Reverse inorder: Right → Root → Left
17 // Accumulates sum of all values seen so far (all greater values)
18 private static void reverseInorder(TreeNode node) {
19 if (node == null) return;
20
21 reverseInorder(node.right); // Process all larger values first
22
23 runningSum += node.val; // Add this node to running sum
24 node.val = runningSum; // Update node's value
25
26 reverseInorder(node.left); // Process all smaller values
27 }
28
29 static void inorder(TreeNode node) {
30 if (node == null) return;
31 inorder(node.left);
32 System.out.print(node.val + " ");
33 inorder(node.right);
34 }
35
36 public static void main(String[] args) {
37 // 4
38 // / \
39 // 1 6
40 // \ / \
41 // 2 5 7
42 TreeNode root = new TreeNode(4);
43 root.left = new TreeNode(1); root.right = new TreeNode(6);
44 root.left.right = new TreeNode(2);
45 root.right.left = new TreeNode(5); root.right.right = new TreeNode(7);
46
47 System.out.print("Before: "); inorder(root); System.out.println();
48 // 1 2 4 5 6 7
49
50 convertBST(root);
51 System.out.print("After: "); inorder(root); System.out.println();
52 // 25 24 22 18 13 7
53 }
54}Output:
Before: [1, 2, 4, 5, 6, 7]
After: [25, 24, 22, 18, 13, 7]
Application 4: Recover BST (Two Nodes Swapped)
Exactly two nodes are swapped by mistake. Find them using inorder traversal and swap their values back.
Original BST (correct): 1, 2, 3, 4, 5, 6, 7
Swapped (3 and 6): 1, 2, 6, 4, 5, 3, 7
↑ ↑
violation 1 violation 2
(6 > 4) (5 > 3)
First violation: prev=6, curr=4 → first = 6 (the prev node)
Second violation: prev=5, curr=3 → second = 3 (the curr node)
Swap first.val and second.val to restore the BST.
ADJACENT case (only one violation):
Correct: 1, 2, 3, 4
Swapped: 1, 3, 2, 4 (2 and 3 swapped)
↑
violation: prev=3, curr=2
First = 3, Second = 2 (same violation — both assigned from same violation)
1public class RecoverBST {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 private static TreeNode first, second, prev;
9
10 public static void recoverTree(TreeNode root) {
11 first = second = prev = null;
12 findViolations(root);
13
14 if (first != null && second != null) {
15 // Swap the values of the two misplaced nodes
16 int temp = first.val;
17 first.val = second.val;
18 second.val = temp;
19 }
20 }
21
22 private static void findViolations(TreeNode node) {
23 if (node == null) return;
24
25 findViolations(node.left);
26
27 // Check for violation in inorder sequence
28 if (prev != null && node.val < prev.val) {
29 if (first == null) first = prev; // First violation: record prev
30 second = node; // Always update second to current
31 }
32
33 prev = node;
34
35 findViolations(node.right);
36 }
37
38 static void inorder(TreeNode n, java.util.List<Integer> r) {
39 if (n==null) return; inorder(n.left,r); r.add(n.val); inorder(n.right,r);
40 }
41
42 public static void main(String[] args) {
43 // 3 Intended BST: 1
44 // / \ / \
45 // 1 4 (3 and 4 are swapped) 3 4 (wait, this isn't right)
46 // / /
47 // 2 2
48 // Let's use: intended [1,2,3], swapped gives root=3, left=1, right=4, right.left=2
49 // Swap 3 and 2: root should be 1, left=2, right=3... Let me use a clear example:
50
51 // Intended: BST with values 1,2,3 → inorder [1,2,3]
52 // Swapped (3 and 1 exchanged at node level):
53 // 3
54 // / \
55 // 2 1 ← 3 and 1 are in wrong positions, inorder gives [2,3,1] violation at 3>1
56 TreeNode root = new TreeNode(3);
57 root.left = new TreeNode(2); root.right = new TreeNode(1);
58
59 java.util.List<Integer> before = new java.util.ArrayList<>();
60 inorder(root, before);
61 System.out.println("Before: " + before); // [2, 3, 1]
62
63 recoverTree(root);
64
65 java.util.List<Integer> after = new java.util.ArrayList<>();
66 inorder(root, after);
67 System.out.println("After: " + after); // [1, 2, 3]
68 }
69}Output:
Before: [2, 3, 1]
After: [1, 2, 3]
Traversal Patterns Summary for BST
PATTERN TRAVERSAL ORDER USE CASE ────────────────────────────────────────────────────────────────── Get sorted output Inorder (L→R→L) Print BST sorted Validate BST Inorder + prev check Is this a valid BST? Kth smallest Inorder, stop at k Find kth smallest Kth largest Reverse inorder Find kth largest Convert to greater tree Reverse inorder Greater sum tree Recover swapped nodes Inorder + violations Fix broken BST Sum of range [lo, hi] Inorder with pruning Range sum query Count nodes in range Inorder with pruning Range count query Convert to sorted array Inorder collect BST → sorted array
Complexity Summary
| Operation | Time | Space | Notes |
|---|---|---|---|
| Inorder traversal | O(n) | O(h) | h = log n balanced, n skewed |
| Validate BST | O(n) | O(h) | One pass, no extra array |
| Kth smallest | O(k) avg | O(h) | Stops early — doesn't visit all nodes |
| Greater sum tree | O(n) | O(h) | Single pass reverse inorder |
| Recover BST | O(n) | O(h) | One inorder pass, O(1) extra pointers |
Common Mistakes
Using int (not long) for the previous value in BST validation. If the BST contains Integer.MIN_VALUE as a node, comparing node.val <= Integer.MIN_VALUE always fails since no valid int is less. Use Long.MIN_VALUE or null for the initial previous value to handle all valid integer inputs.
Recover BST: always updating second but forgetting to only set first once. The first violation sets first = prev once. All subsequent violations update only second = curr. The common bug is setting first at every violation — this overwrites the true first misplaced node with an intermediate one.
Greater sum tree: not resetting the running sum between calls. If runningSum is a class/global variable and convertBST is called multiple times, the second call uses leftover state. Always reset runningSum = 0 at the start of convertBST.
Kth smallest: iterating the full tree instead of stopping early. The iterative approach should return curr.val immediately when count == k. Continuing to iterate wastes time proportional to n−k. The recursive approach should short-circuit using an early return condition.
Interview Questions
Q: Why does inorder traversal of a BST give sorted output?
The BST property guarantees that for every node N: all nodes in N's left subtree have values < N.val, and all in the right subtree have values > N.val. Inorder traversal (Left → Root → Right) visits all of the left subtree (all smaller values) before the current node, and the right subtree (all larger values) after. Since this property holds recursively at every node, the combined output is a non-decreasing sequence — strictly increasing if all values are unique.
Q: How do you find the kth smallest element in a BST without converting to an array?
Use iterative inorder traversal with an explicit stack. Maintain a counter that increments each time a node is visited (popped from stack). Return the node's value as soon as the counter reaches k. This avoids collecting all values into an array and stops as soon as the answer is found. Time: O(k) on average for a balanced tree. Space: O(h) for the stack.
Q: In the Recover BST problem, why might there be only one violation in the inorder sequence?
When the two swapped nodes are adjacent in the inorder sequence (e.g., swapping positions 3 and 4 in [1,2,3,4,5] gives [1,2,4,3,5] — one violation at 4>3), there is exactly one descending pair. When they are non-adjacent (swapping 2 and 4 gives [1,4,3,2,5] — two violations: 4>3 and 3>2), there are two violations. The algorithm handles both: first is set at the first violation's prev, and second is always updated to the current violation's curr. For adjacent swaps, both first and second are set from the single violation.
Summary
BST DFS traversals leverage the BST property to solve problems efficiently:
Inorder (Left → Root → Right): Visits nodes in sorted ascending order. The foundation for validation, kth smallest, and converting to sorted sequences.
Reverse inorder (Right → Root → Left): Visits nodes in descending order. Used for greater sum tree, kth largest, and reverse-sorted operations.
Key applications:
- ›Validate BST — inorder: each value must be strictly greater than previous; or range method: pass min/max bounds down
- ›Kth smallest — inorder iterative: stop after k nodes, O(k) time
- ›Greater sum tree — reverse inorder + running sum: each node becomes sum of all greater values
- ›Recover BST — inorder + violation detection:
first= prev at first violation,second= curr at last violation
All operations are O(n) time and O(h) space (call stack depth). For balanced BSTs, h = O(log n); for skewed BSTs, h = O(n).
In the next topic you will explore BST Operations — floor, ceiling, rank, select, and the BST iterator pattern.
Inorder traversal of a valid BST always produces which output?