BST Operations
Overview
BST operations beyond basic search/insert/delete leverage the BST property to achieve O(log n) for complex queries. Each operation uses the "go left if target is smaller, go right if target is larger" pattern — but applies it to richer questions than simple search.
BST reference for all examples:
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
Sorted sequence (inorder): 1, 3, 4, 6, 7, 8, 10, 13, 14
OPERATION TIME SPACE APPROACH
────────────────────────────────────────────────────────
Floor / Ceil O(h) O(1) BST property traversal
Kth smallest O(h+k) O(h) Inorder stop at k
Kth largest O(h+k) O(h) Reverse inorder stop at k
Range sum [lo, hi] O(k+h) O(h) Inorder with pruning
BST iterator next() O(1) O(h) Lazy stack inorder
Sorted array → BST O(n) O(n) Divide and conquer
Operation 1: Floor and Ceiling
Floor of k: the largest value in the BST that is ≤ k. Ceiling of k: the smallest value in the BST that is ≥ k.
BST inorder: 1, 3, 4, 6, 7, 8, 10, 13, 14
Floor(5) = 4 (largest value ≤ 5)
Floor(7) = 7 (exact match — value equals k)
Floor(0) = null (no value ≤ 0 in the BST)
Ceiling(5) = 6 (smallest value ≥ 5)
Ceiling(7) = 7 (exact match)
Ceiling(15)= null (no value ≥ 15 in the BST)
FLOOR ALGORITHM:
curr = root, result = null
while curr:
if k == curr.val: return curr.val (exact match)
if k < curr.val: go LEFT (root is too big)
if k > curr.val: result = curr.val (root is a candidate — record it)
go RIGHT (might find something bigger ≤ k)
CEILING ALGORITHM (mirror):
curr = root, result = null
while curr:
if k == curr.val: return curr.val (exact match)
if k > curr.val: go RIGHT (root is too small)
if k < curr.val: result = curr.val (root is a candidate — record it)
go LEFT (might find something smaller ≥ k)
1public class BSTFloorCeil {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 // Floor: largest value ≤ k
9 public static Integer floor(TreeNode root, int k) {
10 Integer result = null;
11 TreeNode curr = root;
12
13 while (curr != null) {
14 if (k == curr.val) return k; // Exact match
15
16 if (k < curr.val) {
17 curr = curr.left; // Root too large — go left
18 } else {
19 result = curr.val; // Root is candidate — record it
20 curr = curr.right; // Try to find closer value
21 }
22 }
23
24 return result; // Largest value ≤ k found, or null if none
25 }
26
27 // Ceiling: smallest value ≥ k
28 public static Integer ceil(TreeNode root, int k) {
29 Integer result = null;
30 TreeNode curr = root;
31
32 while (curr != null) {
33 if (k == curr.val) return k; // Exact match
34
35 if (k > curr.val) {
36 curr = curr.right; // Root too small — go right
37 } else {
38 result = curr.val; // Root is candidate — record it
39 curr = curr.left; // Try to find closer value
40 }
41 }
42
43 return result;
44 }
45
46 public static void main(String[] args) {
47 TreeNode root = new TreeNode(8);
48 root.left = new TreeNode(3); root.right = new TreeNode(10);
49 root.left.left = new TreeNode(1); root.left.right = new TreeNode(6);
50 root.right.right = new TreeNode(14);
51 root.left.right.left = new TreeNode(4);
52 root.left.right.right = new TreeNode(7);
53 root.right.right.left = new TreeNode(13);
54
55 System.out.println("Floor(5): " + floor(root, 5)); // 4
56 System.out.println("Floor(7): " + floor(root, 7)); // 7 (exact)
57 System.out.println("Floor(0): " + floor(root, 0)); // null
58 System.out.println("Floor(14): " + floor(root, 14)); // 14 (exact)
59 System.out.println("Floor(15): " + floor(root, 15)); // 14
60
61 System.out.println("Ceil(5): " + ceil(root, 5)); // 6
62 System.out.println("Ceil(7): " + ceil(root, 7)); // 7 (exact)
63 System.out.println("Ceil(15): " + ceil(root, 15)); // null
64 System.out.println("Ceil(0): " + ceil(root, 0)); // 1
65 }
66}Output:
Floor(5): 4
Floor(7): 7
Floor(0): null
Floor(14): 14
Floor(15): 14
Ceil(5): 6
Ceil(7): 7
Ceil(15): null
Ceil(0): 1
Dry Run: Floor(5) on the BST
BST inorder: 1, 3, 4, 6, 7, 8, 10, 13, 14 Floor(5) = 4
curr=8, k=5: 5 < 8 → go left, result=null
curr=3, k=5: 5 > 3 → result=3, go right
curr=6, k=5: 5 < 6 → go left, result=3 (unchanged — 6 > k)
curr=4, k=5: 5 > 4 → result=4, go right
curr=null → return result = 4 ✓
Logic: every time k > curr.val, record curr.val as best floor so far.
Go right to find something larger but still ≤ k.
If nothing found: the last recorded value is the floor.
Operation 2: Range Sum Query [lo, hi]
Find the sum of all values in the BST that fall within the range [lo, hi].
Range sum [4, 10] on BST inorder [1,3,4,6,7,8,10,13,14]: Values in range: 4, 6, 7, 8, 10 Sum = 4+6+7+8+10 = 35 PRUNING with BST property: If node.val < lo: skip left subtree (all values there < node.val < lo) If node.val > hi: skip right subtree (all values there > node.val > hi) Otherwise: include node.val, recurse both sides
1public class BSTRangeSumQuery {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 // Recursive range sum — prunes subtrees outside [lo, hi]
9 public static int rangeSumBST(TreeNode root, int lo, int hi) {
10 if (root == null) return 0;
11
12 // Node value below range — left subtree is entirely below range
13 if (root.val <= lo) {
14 return rangeSumBST(root.right, lo, hi);
15 }
16
17 // Node value above range — right subtree is entirely above range
18 if (root.val >= hi) {
19 return rangeSumBST(root.left, lo, hi);
20 }
21
22 // Node value within range — include it and recurse both sides
23 return root.val
24 + rangeSumBST(root.left, lo, hi)
25 + rangeSumBST(root.right, lo, hi);
26 }
27
28 // Strictly: for lo < node.val <= hi check (adjust boundaries as needed)
29 public static int rangeSumStrict(TreeNode root, int lo, int hi) {
30 if (root == null) return 0;
31 int sum = 0;
32
33 if (root.val > lo) sum += rangeSumStrict(root.left, lo, hi); // Might have values in range
34 if (root.val >= lo && root.val <= hi) sum += root.val; // Include if in range
35 if (root.val < hi) sum += rangeSumStrict(root.right, lo, hi); // Might have values in range
36
37 return sum;
38 }
39
40 public static void main(String[] args) {
41 TreeNode root = new TreeNode(8);
42 root.left = new TreeNode(3); root.right = new TreeNode(10);
43 root.left.left = new TreeNode(1); root.left.right = new TreeNode(6);
44 root.right.right = new TreeNode(14);
45 root.left.right.left = new TreeNode(4);
46 root.left.right.right = new TreeNode(7);
47 root.right.right.left = new TreeNode(13);
48
49 System.out.println("Sum [4,10]: " + rangeSumStrict(root, 4, 10)); // 35 (4+6+7+8+10)
50 System.out.println("Sum [1,14]: " + rangeSumStrict(root, 1, 14)); // 67 (all)
51 System.out.println("Sum [9,12]: " + rangeSumStrict(root, 9, 12)); // 10
52 System.out.println("Sum [15,20]:" + rangeSumStrict(root, 15, 20)); // 0
53 }
54}Output:
Sum [4,10]: 35 (4+6+7+8+10)
Sum [1,14]: 67 (1+3+4+6+7+8+10+13+14)
Sum [9,12]: 10 (10 only)
Sum [15,20]: 0 (nothing in range)
Operation 3: BST Iterator
Design an iterator that returns BST values in ascending order one at a time. Supports next() (returns next smallest) and hasNext() (returns true if more values exist).
BST: 4
/ \
2 6
/ \ / \
1 3 5 7
Iterator sequence: 1, 2, 3, 4, 5, 6, 7 (inorder)
LAZY STACK APPROACH:
Initialize: push all left-spine nodes onto stack
Stack after init: [4, 2, 1] (1 is on top — smallest)
next() call 1:
Pop 1 (smallest) → return 1
Push right subtree of 1's left spine: 1 has no right → nothing pushed
Stack: [4, 2]
next() call 2:
Pop 2 → return 2
Push right subtree of 2: right=3, push 3 and its left spine
Stack: [4, 3]
next() call 3:
Pop 3 → return 3
3 has no right → nothing pushed
Stack: [4]
next() call 4:
Pop 4 → return 4
Push right subtree of 4: right=6, push 6→5 (left spine of 6's subtree)
Stack: [6, 5]
... continues for 5, 6, 7
1import java.util.Deque;
2import java.util.ArrayDeque;
3
4public class BSTIterator {
5
6 static class TreeNode {
7 int val; TreeNode left, right;
8 TreeNode(int v) { val = v; }
9 }
10
11 private Deque<TreeNode> stack = new ArrayDeque<>();
12
13 public BSTIterator(TreeNode root) {
14 pushLeftSpine(root); // Initialize with all left-spine nodes
15 }
16
17 // Push current node and all left descendants onto stack
18 private void pushLeftSpine(TreeNode node) {
19 while (node != null) {
20 stack.push(node);
21 node = node.left;
22 }
23 }
24
25 // Returns the next smallest value — O(1) amortised
26 public int next() {
27 TreeNode node = stack.pop(); // Pop current minimum
28 pushLeftSpine(node.right); // Push right child's left spine
29 return node.val;
30 }
31
32 // Returns true if more elements exist — O(1)
33 public boolean hasNext() {
34 return !stack.isEmpty();
35 }
36
37 public static void main(String[] args) {
38 // 4
39 // / \
40 // 2 6
41 // / \ / \
42 // 1 3 5 7
43 TreeNode root = new TreeNode(4);
44 root.left = new TreeNode(2); root.right = new TreeNode(6);
45 root.left.left = new TreeNode(1); root.left.right = new TreeNode(3);
46 root.right.left = new TreeNode(5); root.right.right = new TreeNode(7);
47
48 BSTIterator it = new BSTIterator(root);
49 StringBuilder sb = new StringBuilder();
50
51 while (it.hasNext()) {
52 sb.append(it.next()).append(" ");
53 }
54 System.out.println("Iterator: " + sb.toString().trim());
55 // Iterator: 1 2 3 4 5 6 7
56 }
57}Output:
Iterator: 1 2 3 4 5 6 7
Operation 4: Kth Largest Element
Use reverse inorder (Right → Root → Left) — visits nodes in descending order. Stop after visiting k nodes.
1public class BSTKthLargest {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 private static int count = 0;
9 private static int result = -1;
10
11 public static int kthLargest(TreeNode root, int k) {
12 count = 0; result = -1;
13 reverseInorder(root, k);
14 return result;
15 }
16
17 // Reverse inorder: Right → Root → Left (descending order)
18 private static void reverseInorder(TreeNode node, int k) {
19 if (node == null || count >= k) return;
20
21 reverseInorder(node.right, k); // Larger values first
22
23 count++;
24 if (count == k) {
25 result = node.val;
26 return;
27 }
28
29 reverseInorder(node.left, k);
30 }
31
32 // Iterative version
33 public static int kthLargestIterative(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 // Push all right children (go to maximum)
40 while (curr != null) {
41 stack.push(curr);
42 curr = curr.right;
43 }
44
45 curr = stack.pop();
46 count++;
47
48 if (count == k) return curr.val; // Found kth largest
49
50 curr = curr.left; // Move to smaller values
51 }
52
53 return -1;
54 }
55
56 public static void main(String[] args) {
57 TreeNode root = new TreeNode(8);
58 root.left = new TreeNode(3); root.right = new TreeNode(10);
59 root.left.left = new TreeNode(1); root.left.right = new TreeNode(6);
60 root.right.right = new TreeNode(14);
61 root.left.right.left = new TreeNode(4);
62 root.left.right.right = new TreeNode(7);
63 root.right.right.left = new TreeNode(13);
64
65 // Descending: 14, 13, 10, 8, 7, 6, 4, 3, 1
66 System.out.println("1st largest: " + kthLargest(root, 1)); // 14
67 System.out.println("2nd largest: " + kthLargest(root, 2)); // 13
68 System.out.println("3rd largest: " + kthLargestIterative(root, 3)); // 10
69 System.out.println("9th largest: " + kthLargest(root, 9)); // 1 (smallest)
70 }
71}Output:
1st largest: 14
2nd largest: 13
3rd largest: 10
9th largest: 1
Operation 5: Convert Sorted Array to Balanced BST
Given a sorted array, build the height-balanced BST — each half of the array becomes a subtree.
Sorted array: [-10, -3, 0, 5, 9]
Mid = index 2 → value 0 → ROOT
Left half: [-10, -3] → mid = 1 → value -3 → left child of 0
Left of -3: [-10] → leaf
Right of -3: [] → null
Right half: [5, 9] → mid = 1 → value 9 → right child of 0
Left of 9: [5] → leaf
Right of 9: [] → null
Resulting BST:
0
/ \
-3 9
/ /
-10 5
Height = 2 ✓ — perfectly balanced for 5 elements
1public class SortedArrayToBST {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 public static TreeNode sortedArrayToBST(int[] nums) {
9 return buildBST(nums, 0, nums.length - 1);
10 }
11
12 private static TreeNode buildBST(int[] nums, int lo, int hi) {
13 if (lo > hi) return null; // Base case: empty subarray
14
15 int mid = lo + (hi - lo) / 2; // Middle element becomes root
16 TreeNode root = new TreeNode(nums[mid]);
17
18 root.left = buildBST(nums, lo, mid - 1); // Left half
19 root.right = buildBST(nums, mid + 1, hi); // Right half
20
21 return root;
22 }
23
24 static void inorder(TreeNode n, java.util.List<Integer> r) {
25 if (n==null) return; inorder(n.left,r); r.add(n.val); inorder(n.right,r);
26 }
27
28 public static void main(String[] args) {
29 int[] sorted = {-10, -3, 0, 5, 9};
30 TreeNode root = sortedArrayToBST(sorted);
31
32 java.util.List<Integer> result = new java.util.ArrayList<>();
33 inorder(root, result);
34 System.out.println("Inorder: " + result); // [-10, -3, 0, 5, 9]
35 System.out.println("Root: " + root.val); // 0
36 System.out.println("Height: " + height(root)); // 2
37
38 // Larger example
39 int[] sorted2 = {1, 2, 3, 4, 5, 6, 7};
40 TreeNode root2 = sortedArrayToBST(sorted2);
41 System.out.println("Root of 1-7 BST: " + root2.val); // 4
42 }
43
44 static int height(TreeNode n) {
45 if (n == null) return -1;
46 return 1 + Math.max(height(n.left), height(n.right));
47 }
48}Output:
Inorder: [-10, -3, 0, 5, 9]
Root: 0
Height: 2
Root of 1-7 BST: 4
Operations Summary
OPERATION ALGORITHM TIME SPACE
──────────────────────────────────────────────────────────────────
Floor(k) Track best candidate, go right O(h) O(1)
when k > curr; go left when k < curr
Ceil(k) Mirror of floor O(h) O(1)
Range sum [lo,hi] Inorder with left/right pruning O(k+h) O(h)
BST iterator Lazy stack, push left spine O(1)amort O(h)
Kth largest Reverse inorder, stop at k O(h+k) O(h)
Sorted arr → BST Mid as root, recurse halves O(n) O(n)
Common Mistakes
Floor: returning root.val without searching right. When k > root.val, root is a candidate but a larger value ≤ k might exist in the right subtree. Always record root.val and continue searching right. Returning immediately when k > root.val gives floor(k) = root.val, which is wrong whenever a closer value exists to the right.
BST iterator: forgetting to push the right child's left spine in next(). After popping the current minimum, you must push the right child's entire left spine onto the stack. Forgetting this causes the iterator to skip entire right subtrees — missing values.
Range sum: not pruning when node.val == lo or node.val == hi. The boundary check must be inclusive: if lo <= node.val <= hi, include the node. A common off-by-one is using strict < or > when <= or >= is needed.
Sorted array to BST: using (lo + hi) / 2 instead of lo + (hi - lo) / 2. For large arrays where lo + hi overflows 32-bit integers, the latter is overflow-safe. This is especially important in C++ and Java where integer overflow is silent.
Interview Questions
Q: Why is floor(k) a "candidate + go right" pattern?
When k > root.val, root is a valid floor candidate (it's ≤ k), but there might be a larger value ≤ k hiding in the right subtree. Record root.val as the current best, then go right to see if anything closer to k exists. If no larger value ≤ k is found, the last recorded candidate is the answer. When k < root.val, root is too large for a floor — floor must be in the left subtree, so go left without recording.
Q: How is the BST iterator O(1) amortised rather than O(n) per call?
Across all n calls to next(), each node is pushed onto the stack exactly once and popped exactly once — O(2n) = O(n) total work for n calls. Per call, the amortised cost is O(n)/n = O(1). A single next() call may push O(h) nodes (a full left spine), but this happens rarely — specifically only for nodes that have right children with long left spines. The total pushes across all calls remains O(n).
Q: Why does using the array midpoint as root guarantee a balanced BST?
With lo and hi as the current subarray boundaries, mid = (lo+hi)/2 divides the elements as evenly as possible: the left subarray has ⌊(n-1)/2⌋ elements and the right has ⌈(n-1)/2⌉ elements (or vice versa). The height difference between left and right subtrees is at most 1 at every node by induction. The resulting tree's height is ⌊log₂(n)⌋ — the minimum possible for n nodes.
Summary
BST operations beyond basic search/insert/delete:
Floor and Ceiling: Follow BST property tracking the best candidate. Floor: record node when k > node.val, go right; go left when k < node.val. Ceiling mirrors this. Both O(h), O(1) space.
Range sum: Inorder traversal with pruning — skip left subtree if node.val ≤ lo; skip right subtree if node.val ≥ hi. O(k + h) where k = values in range.
BST Iterator: Lazy stack initialised with all left-spine nodes. next() pops the minimum, pushes right child's left spine. O(1) amortised per call, O(h) space.
Kth largest: Reverse inorder (right → root → left) iterative with stack. Stop at kth node. O(h + k) time, O(h) space.
Sorted array → BST: Recursively use the middle element as root. Left half becomes left subtree, right half becomes right subtree. O(n) time, O(n) space (output tree).
In the next topic you will explore BST Practice Problems — applying all BST operations to classic interview problems with recognition signals and solution patterns.
Floor of key k in a BST is defined as the largest value ≤ k. When does the floor lie in the RIGHT subtree?