DSA Tutorial
🔍
BST BFS Traversal
BFS on a BST — What's Different
BFS (level order traversal) works identically on any binary tree — use a queue, process nodes level by level. On a BST, however, the level-order output does not produce sorted values. The BST property organises values relative to parents and ancestors, not within a horizontal level.
BST: 8 Level order output:
/ \
3 10 Level 0: [8]
/ \ \ Level 1: [3, 10]
1 6 14 Level 2: [1, 6, 14]
/ \ / Level 3: [4, 7, 13]
4 7 13
Level 0: [8] — just the root
Level 1: [3, 10] — 3 < 10 (happens to be sorted here)
Level 2: [1, 6, 14] — 1 < 6 < 14 (happens to be sorted here)
Level 3: [4, 7, 13] — not necessarily sorted at every level
Compare with inorder: [1, 3, 4, 6, 7, 8, 10, 13, 14] — always sorted
Level order is NOT sorted. BST's sorted property lives in DFS inorder only.
BUT BST level order has its own useful properties:
✓ Root appears first (level 0)
✓ Each node's left child < node < right child (BST property per node)
✓ Level-order uniquely reconstructs the BST (with BST property)
✓ Useful for width, level-sum, and nearest-to-value queries
Standard Level Order — BST
Java
1import java.util.*;
2
3public class BSTLevelOrder {
4
5 static class TreeNode {
6 int val; TreeNode left, right;
7 TreeNode(int v) { val = v; }
8 }
9
10 // Level order traversal — returns list of levels
11 public static List<List<Integer>> levelOrder(TreeNode root) {
12 List<List<Integer>> result = new ArrayList<>();
13 if (root == null) return result;
14
15 Queue<TreeNode> queue = new ArrayDeque<>();
16 queue.offer(root);
17
18 while (!queue.isEmpty()) {
19 int levelSize = queue.size();
20 List<Integer> level = new ArrayList<>();
21
22 for (int i = 0; i < levelSize; i++) {
23 TreeNode node = queue.poll();
24 level.add(node.val);
25
26 if (node.left != null) queue.offer(node.left);
27 if (node.right != null) queue.offer(node.right);
28 }
29
30 result.add(level);
31 }
32
33 return result;
34 }
35
36 // Flat level order — single list, no level boundaries
37 public static List<Integer> levelOrderFlat(TreeNode root) {
38 List<Integer> result = new ArrayList<>();
39 if (root == null) return result;
40
41 Queue<TreeNode> queue = new ArrayDeque<>();
42 queue.offer(root);
43
44 while (!queue.isEmpty()) {
45 TreeNode node = queue.poll();
46 result.add(node.val);
47 if (node.left != null) queue.offer(node.left);
48 if (node.right != null) queue.offer(node.right);
49 }
50
51 return result;
52 }
53
54 public static void main(String[] args) {
55 TreeNode root = new TreeNode(8);
56 root.left = new TreeNode(3); root.right = new TreeNode(10);
57 root.left.left = new TreeNode(1); root.left.right = new TreeNode(6);
58 root.right.right = new TreeNode(14);
59 root.left.right.left = new TreeNode(4);
60 root.left.right.right = new TreeNode(7);
61 root.right.right.left = new TreeNode(13);
62
63 System.out.println("Level order: " + levelOrder(root));
64 // [[8], [3, 10], [1, 6, 14], [4, 7, 13]]
65
66 System.out.println("Level order flat: " + levelOrderFlat(root));
67 // [8, 3, 10, 1, 6, 14, 4, 7, 13]
68
69 System.out.println("Note: inorder gives sorted [1,3,4,6,7,8,10,13,14]");
70 System.out.println("Level order does NOT give sorted output for a BST.");
71 }
72}Output:
Level order: [[8], [3, 10], [1, 6, 14], [4, 7, 13]]
Level order flat: [8, 3, 10, 1, 6, 14, 4, 7, 13]
Note: inorder gives sorted [1,3,4,6,7,8,10,13,14]
Level order does NOT give sorted output for a BST.
BST-Specific BFS: Validate BST Level by Level
Pass [min, max] range constraints through the queue alongside each node. Check each dequeued node is within its inherited range.
Validation using BFS with ranges: Start: queue = [(node=8, min=-∞, max=+∞)] Process (8, -∞, +∞): 8 within (-∞, +∞) ✓ Enqueue left child 3 with range (-∞, 8) Enqueue right child 10 with range (8, +∞) Process (3, -∞, 8): 3 within (-∞, 8) ✓ Enqueue left child 1 with range (-∞, 3) Enqueue right child 6 with range (3, 8) Process (10, 8, +∞): 10 within (8, +∞) ✓ Enqueue right child 14 with range (10, +∞) ... INVALID tree example: (node=4, min=3, max=8) but 4 is at an invalid position → caught immediately
Java
1import java.util.*;
2
3public class BSTValidateBFS {
4
5 static class TreeNode {
6 int val; TreeNode left, right;
7 TreeNode(int v) { val = v; }
8 }
9
10 public static boolean isValidBST(TreeNode root) {
11 if (root == null) return true;
12
13 // Queue entries: [node, min_allowed, max_allowed]
14 Queue<Object[]> queue = new ArrayDeque<>();
15 queue.offer(new Object[]{root, Long.MIN_VALUE, Long.MAX_VALUE});
16
17 while (!queue.isEmpty()) {
18 Object[] entry = queue.poll();
19 TreeNode node = (TreeNode) entry[0];
20 long min = (long) entry[1];
21 long max = (long) entry[2];
22
23 // Node value must be strictly within (min, max)
24 if (node.val <= min || node.val >= max) return false;
25
26 if (node.left != null)
27 queue.offer(new Object[]{node.left, min, (long) node.val});
28
29 if (node.right != null)
30 queue.offer(new Object[]{node.right, (long) node.val, max});
31 }
32
33 return true;
34 }
35
36 public static void main(String[] args) {
37 // Valid: 2 / 1, 3
38 TreeNode valid = new TreeNode(2);
39 valid.left = new TreeNode(1); valid.right = new TreeNode(3);
40 System.out.println("Valid BFS: " + isValidBST(valid)); // true
41
42 // Invalid: 5 / 1, 4 / _, 3 (4 < 5 but in right subtree)
43 TreeNode invalid = new TreeNode(5);
44 invalid.left = new TreeNode(1); invalid.right = new TreeNode(4);
45 invalid.right.left = new TreeNode(3); invalid.right.right = new TreeNode(6);
46 System.out.println("Invalid BFS: " + isValidBST(invalid)); // false
47 }
48}Output:
Valid BFS: true
Invalid BFS: false
Application: Level Sum and Level Maximum in BST
Compute the sum or maximum of all nodes at each level — useful for queries like "find the level with maximum sum".
Java
1import java.util.*;
2
3public class BSTLevelSumMax {
4
5 static class TreeNode {
6 int val; TreeNode left, right;
7 TreeNode(int v) { val = v; }
8 }
9
10 // Returns list of (sum, max) per level
11 public static void levelSumAndMax(TreeNode root) {
12 if (root == null) return;
13
14 Queue<TreeNode> queue = new ArrayDeque<>();
15 queue.offer(root);
16 int level = 0;
17
18 while (!queue.isEmpty()) {
19 int levelSize = queue.size();
20 long sum = 0;
21 int max = Integer.MIN_VALUE;
22
23 for (int i = 0; i < levelSize; i++) {
24 TreeNode node = queue.poll();
25 sum += node.val;
26 max = Math.max(max, node.val);
27
28 if (node.left != null) queue.offer(node.left);
29 if (node.right != null) queue.offer(node.right);
30 }
31
32 System.out.printf("Level %d: sum=%d, max=%d%n", level, sum, max);
33 level++;
34 }
35 }
36
37 // Find level with maximum sum
38 public static int maxLevelSum(TreeNode root) {
39 if (root == null) return 0;
40
41 Queue<TreeNode> queue = new ArrayDeque<>();
42 queue.offer(root);
43 int maxSum = Integer.MIN_VALUE;
44 int maxLevel = 1;
45 int level = 1;
46
47 while (!queue.isEmpty()) {
48 int levelSize = queue.size();
49 int sum = 0;
50
51 for (int i = 0; i < levelSize; i++) {
52 TreeNode node = queue.poll();
53 sum += node.val;
54 if (node.left != null) queue.offer(node.left);
55 if (node.right != null) queue.offer(node.right);
56 }
57
58 if (sum > maxSum) { maxSum = sum; maxLevel = level; }
59 level++;
60 }
61
62 return maxLevel;
63 }
64
65 public static void main(String[] args) {
66 // 8
67 // / \
68 // 3 10
69 // / \ \
70 // 1 6 14
71 // / \ /
72 // 4 7 13
73 TreeNode root = new TreeNode(8);
74 root.left = new TreeNode(3); root.right = new TreeNode(10);
75 root.left.left = new TreeNode(1); root.left.right = new TreeNode(6);
76 root.right.right = new TreeNode(14);
77 root.left.right.left = new TreeNode(4);
78 root.left.right.right = new TreeNode(7);
79 root.right.right.left = new TreeNode(13);
80
81 levelSumAndMax(root);
82 System.out.println("Max level sum at level: " + maxLevelSum(root));
83 }
84}Output:
Level 0: sum=8, max=8
Level 1: sum=13, max=10
Level 2: sum=21, max=14
Level 3: sum=24, max=13
Max level sum at level: 4 (level 3, 1-indexed)
Application: Serialize and Deserialize BST Using Level Order
Level order serialization stores nodes in BFS order. For a BST, deserialization can reconstruct the unique tree using the BST property.
SERIALIZE (BFS): BST: 8, [3,10], [1,6,14], [4,7,13] Output string: "8,3,10,1,6,14,4,7,13" DESERIALIZE (BST-specific — no nulls needed): Read 8 → root Read 3 → 3 < 8 → left child of 8 Read 10 → 10 > 8 → right child of 8 Read 1 → 1 < 8 → left side; 1 < 3 → left child of 3 Read 6 → 6 < 8 → left side; 6 > 3 → right child of 3 ... The BST property determines each value's position without null markers. This is why BST serialization can be more compact than general tree serialization.
Java
1import java.util.*;
2
3public class BSTSerializeDeserialize {
4
5 static class TreeNode {
6 int val; TreeNode left, right;
7 TreeNode(int v) { val = v; }
8 }
9
10 // Serialize BST using level order
11 public static String serialize(TreeNode root) {
12 if (root == null) return "";
13
14 StringBuilder sb = new StringBuilder();
15 Queue<TreeNode> queue = new ArrayDeque<>();
16 queue.offer(root);
17
18 while (!queue.isEmpty()) {
19 TreeNode node = queue.poll();
20 sb.append(node.val).append(",");
21 if (node.left != null) queue.offer(node.left);
22 if (node.right != null) queue.offer(node.right);
23 }
24
25 // Remove trailing comma
26 return sb.substring(0, sb.length() - 1);
27 }
28
29 // Deserialize BST from level order string
30 // Uses BST property — no null markers needed
31 public static TreeNode deserialize(String data) {
32 if (data == null || data.isEmpty()) return null;
33
34 String[] vals = data.split(",");
35 TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
36 Queue<int[]> q = new ArrayDeque<>(); // [min, max] ranges
37 Queue<TreeNode> parents = new ArrayDeque<>();
38
39 parents.offer(root);
40 q.offer(new int[]{Integer.MIN_VALUE, Integer.MAX_VALUE});
41
42 int i = 1;
43 while (i < vals.length && !parents.isEmpty()) {
44 TreeNode parent = parents.poll();
45 int[] range = q.poll();
46 int val = Integer.parseInt(vals[i]);
47
48 // Try to insert as left child (val < parent.val and val > range[0])
49 if (val > range[0] && val < parent.val) {
50 parent.left = new TreeNode(val);
51 parents.offer(parent.left);
52 q.offer(new int[]{range[0], parent.val});
53 i++;
54 // Now try the next value as right child of same parent
55 if (i < vals.length) {
56 val = Integer.parseInt(vals[i]);
57 }
58 }
59
60 // Try to insert as right child
61 if (i < vals.length) {
62 val = Integer.parseInt(vals[i]);
63 if (val > parent.val && val < range[1]) {
64 parent.right = new TreeNode(val);
65 parents.offer(parent.right);
66 q.offer(new int[]{parent.val, range[1]});
67 i++;
68 }
69 }
70 }
71
72 return root;
73 }
74
75 static void inorder(TreeNode n, List<Integer> r) {
76 if (n == null) return; inorder(n.left, r); r.add(n.val); inorder(n.right, r);
77 }
78
79 public static void main(String[] args) {
80 TreeNode root = new TreeNode(4);
81 root.left = new TreeNode(2); root.right = new TreeNode(6);
82 root.left.left = new TreeNode(1); root.left.right = new TreeNode(3);
83 root.right.left = new TreeNode(5); root.right.right = new TreeNode(7);
84
85 String serialized = serialize(root);
86 System.out.println("Serialized: " + serialized); // 4,2,6,1,3,5,7
87
88 TreeNode restored = deserialize(serialized);
89 List<Integer> result = new ArrayList<>();
90 inorder(restored, result);
91 System.out.println("Deserialized inorder: " + result); // [1,2,3,4,5,6,7]
92 }
93}Output:
Serialized: 4,2,6,1,3,5,7
Deserialized inorder: [1, 2, 3, 4, 5, 6, 7]
Application: Find Nodes at Depth K
Return all nodes at exactly depth k from the root using BFS — the most natural traversal for this query.
Java
1import java.util.*;
2
3public class NodesAtDepthK {
4
5 static class TreeNode {
6 int val; TreeNode left, right;
7 TreeNode(int v) { val = v; }
8 }
9
10 public static List<Integer> nodesAtDepthK(TreeNode root, int k) {
11 List<Integer> result = new ArrayList<>();
12 if (root == null) return result;
13
14 Queue<TreeNode> queue = new ArrayDeque<>();
15 queue.offer(root);
16 int depth = 0;
17
18 while (!queue.isEmpty()) {
19 int levelSize = queue.size();
20
21 if (depth == k) {
22 // All nodes in queue at this point are at depth k
23 while (!queue.isEmpty()) {
24 result.add(queue.poll().val);
25 }
26 return result;
27 }
28
29 for (int i = 0; i < levelSize; i++) {
30 TreeNode node = queue.poll();
31 if (node.left != null) queue.offer(node.left);
32 if (node.right != null) queue.offer(node.right);
33 }
34
35 depth++;
36 }
37
38 return result; // k > tree height — no nodes at depth k
39 }
40
41 public static void main(String[] args) {
42 TreeNode root = new TreeNode(8);
43 root.left = new TreeNode(3); root.right = new TreeNode(10);
44 root.left.left = new TreeNode(1); root.left.right = new TreeNode(6);
45 root.right.right = new TreeNode(14);
46 root.left.right.left = new TreeNode(4);
47 root.left.right.right = new TreeNode(7);
48 root.right.right.left = new TreeNode(13);
49
50 System.out.println("Depth 0: " + nodesAtDepthK(root, 0)); // [8]
51 System.out.println("Depth 1: " + nodesAtDepthK(root, 1)); // [3, 10]
52 System.out.println("Depth 2: " + nodesAtDepthK(root, 2)); // [1, 6, 14]
53 System.out.println("Depth 3: " + nodesAtDepthK(root, 3)); // [4, 7, 13]
54 System.out.println("Depth 5: " + nodesAtDepthK(root, 5)); // []
55 }
56}Output:
Depth 0: [8]
Depth 1: [3, 10]
Depth 2: [1, 6, 14]
Depth 3: [4, 7, 13]
Depth 5: []
BFS vs DFS for BST: When to Choose
USE BFS (level order) WHEN: ✓ Need nodes at a specific depth k → collect entire level k ✓ Need level-by-level aggregation → sum, average, max per level ✓ Need width or structure of tree → maximum width, level count ✓ Validating BST structurally level by level → range-based BFS validation ✓ Serialize/deserialize by level → compact level-order encoding ✓ "Closest to root" queries → BFS finds nearest first USE DFS (inorder/preorder) WHEN: ✓ Need sorted output → inorder traversal ✓ BST search, insert, delete → follow BST property ✓ Find min/max → follow left/right pointers ✓ Kth smallest/largest → inorder, stop at k ✓ Floor/ceiling → BST property traversal ✓ Range queries [lo, hi] → inorder with pruning ✓ Path-based problems → DFS naturally follows paths SUMMARY: BST sorted properties → DFS inorder Level/structural properties → BFS Validation → either (both O(n)) For most BST interview problems → DFS is preferred BFS on BST is less common but tested in level-based problems
Complexity Summary
| Operation | Time | Space | Notes |
|---|---|---|---|
| Level order BFS | O(n) | O(w) | w = max level width ≤ n/2 |
| BFS validate | O(n) | O(n) | Queue holds ranges too |
| Level sum/max | O(n) | O(w) | Standard BFS |
| Nodes at depth k | O(n) worst | O(w) | Must traverse to level k |
| Serialize BFS | O(n) | O(n) | All nodes visited once |
| Deserialize BFS | O(n) | O(n) | Reconstruct from level order |
Common Mistakes
Assuming level order output of a BST is sorted. It is not. The BST property guarantees left < parent < right at each node, but nodes at the same level are unordered relative to each other. For sorted output, always use inorder traversal.
Using queue.shift() in JavaScript BFS without considering O(n) cost. Array.shift() is O(n). For large BSTs, using it in BFS results in O(n²) total. Use an index pointer or a proper deque implementation for performance-critical code.
Forgetting to pass the [min, max] range when BFS-validating a BST. The range for each node must be inherited from its parent and ancestors. Left child gets (parent_min, parent_val) and right child gets (parent_val, parent_max). Omitting the range and checking only node.val vs parent.val misses deeper constraint violations.
Not resetting depth counter correctly for nodes at depth k. BFS visits levels sequentially — process all level-0 nodes before level-1, etc. The depth counter increments only after all nodes at the current level are processed. Incrementing inside the inner loop gives wrong depth values.
Summary
BFS traversal on a BST visits nodes level by level using a queue. Unlike DFS inorder, level order does not produce sorted output — the BST's sorted property only surfaces in inorder traversal.
Four BST-specific BFS applications:
| Application | Key technique |
|---|---|
| Validate BST (BFS) | Enqueue each node with its [min, max] range; check on dequeue |
| Level sum/max | Accumulate per level using levelSize = queue.size() before inner loop |
| Nodes at depth k | BFS until depth counter reaches k; return entire queue contents |
| Serialize/deserialize | Serialize via flat BFS; deserialize using BST property to place values |
When to choose BFS over DFS for BST:
- ›Level-based queries (depth k, width, sum per level) → BFS
- ›Sorted queries (kth smallest, range, floor/ceil) → DFS inorder
- ›Validation → either approach works; DFS range method is more common
In the next topic you will explore BST Operations — Floor, Ceil, Range Queries, and Iterator — applying BST traversal patterns to classic interval and streaming problems.
Suggested Quiz
In a valid BST level order traversal, what can you say about elements at the same level?
1/6