BST Basics
What Is a Binary Search Tree?
A Binary Search Tree (BST) is a binary tree with one additional ordering rule on node values:
BST PROPERTY (must hold at EVERY node):
For any node N:
ALL values in N's LEFT subtree < N.val
ALL values in N's RIGHT subtree > N.val
This is recursive — the property applies at every single node.
VALID BST:
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
At node 8: left subtree {1,3,4,6,7} < 8 < right subtree {10,13,14} ✓
At node 3: left subtree {1} < 3 < right subtree {4,6,7} ✓
At node 10: no left, right subtree {13,14} > 10 ✓
At node 6: left {4} < 6 < right {7} ✓
INVALID BST — looks correct but violates property:
5
/ \
3 8
/
4 ← 4 < 5 but is in the RIGHT subtree of 5 ✗
The mistake: 4 is in the right subtree of 5, but 4 < 5.
Checking only parent-child pairs misses this.
You must verify ALL ancestors.
BST vs Sorted Array — Why BST?
OPERATION Sorted Array BST (balanced) BST (worst-skewed) ────────────────────────────────────────────────────────────────── Search O(log n) O(log n) O(n) Insert O(n) O(log n) O(n) Delete O(n) O(log n) O(n) Min/Max O(1) O(log n) O(n) Inorder O(n) O(n) O(n) Floor/Ceil O(log n) O(log n) O(n) KEY INSIGHT: A sorted array is fast for search but slow for insert/delete because shifting elements is O(n). A balanced BST gives O(log n) for ALL three operations — search, insert, and delete. This is why BSTs (and their balanced variants: AVL, Red-Black, TreeMap) are used in databases and ordered-set implementations.
Operation 1: Search
Follow the BST property at each step — go left if target < current, go right if target > current. Stop when found or when you hit null (not present).
Search for 6 in the BST:
8
/ \
3 10
/ \
1 6
/ \
4 7
Step 1: curr=8, 6 < 8 → go left
Step 2: curr=3, 6 > 3 → go right
Step 3: curr=6, 6 == 6 → FOUND ✓
Search for 5:
Step 1: curr=8, 5 < 8 → go left
Step 2: curr=3, 5 > 3 → go right
Step 3: curr=6, 5 < 6 → go left
Step 4: curr=4, 5 > 4 → go right
Step 5: curr=null → NOT FOUND, return -1
1public class BSTSearch {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 // Iterative search — O(h) time, O(1) space
9 public static TreeNode searchIterative(TreeNode root, int target) {
10 TreeNode curr = root;
11
12 while (curr != null) {
13 if (target == curr.val) return curr; // Found
14 else if (target < curr.val) curr = curr.left; // Go left
15 else curr = curr.right; // Go right
16 }
17
18 return null; // Not found
19 }
20
21 // Recursive search — O(h) time, O(h) space (call stack)
22 public static TreeNode searchRecursive(TreeNode root, int target) {
23 if (root == null) return null; // Not found
24 if (target == root.val) return root; // Found
25 if (target < root.val) return searchRecursive(root.left, target);
26 else return searchRecursive(root.right, target);
27 }
28
29 public static void main(String[] args) {
30 // 8
31 // / \
32 // 3 10
33 // / \ \
34 // 1 6 14
35 // / \ /
36 // 4 7 13
37 TreeNode root = new TreeNode(8);
38 root.left = new TreeNode(3); root.right = new TreeNode(10);
39 root.left.left = new TreeNode(1); root.left.right = new TreeNode(6);
40 root.right.right = new TreeNode(14);
41 root.left.right.left = new TreeNode(4);
42 root.left.right.right = new TreeNode(7);
43 root.right.right.left = new TreeNode(13);
44
45 System.out.println(searchIterative(root, 6) != null ? "Found 6" : "Not found"); // Found 6
46 System.out.println(searchIterative(root, 5) != null ? "Found 5" : "Not found"); // Not found
47 System.out.println(searchRecursive(root, 13) != null ? "Found 13" : "Not found"); // Found 13
48 }
49}Output:
Found 6
Not found
Found 13
Operation 2: Insert
Insert a new value by searching for its correct position and adding a new leaf node there.
Insert 5 into the BST:
8 After inserting 5:
/ \
3 10 8
/ \ / \
1 6 3 10
/ \ / \
4 7 1 6
/ \
4 7
\
5 ← new leaf
Steps:
curr=8, 5 < 8 → go left
curr=3, 5 > 3 → go right
curr=6, 5 < 6 → go left
curr=4, 5 > 4 → go right
curr=null → INSERT 5 as right child of 4 ✓
1public class BSTInsert {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 // Iterative insert — O(h) time, O(1) space
9 public static TreeNode insertIterative(TreeNode root, int val) {
10 TreeNode newNode = new TreeNode(val);
11
12 if (root == null) return newNode; // Empty tree
13
14 TreeNode curr = root, parent = null;
15
16 while (curr != null) {
17 parent = curr;
18 if (val < curr.val) curr = curr.left;
19 else if (val > curr.val) curr = curr.right;
20 else return root; // Duplicate — no insert (or handle as needed)
21 }
22
23 // Attach new node to parent
24 if (val < parent.val) parent.left = newNode;
25 else parent.right = newNode;
26
27 return root;
28 }
29
30 // Recursive insert — O(h) time, O(h) space
31 public static TreeNode insertRecursive(TreeNode root, int val) {
32 if (root == null) return new TreeNode(val); // Insert here
33
34 if (val < root.val) root.left = insertRecursive(root.left, val);
35 else if (val > root.val) root.right = insertRecursive(root.right, val);
36 // val == root.val: duplicate, do nothing
37
38 return root;
39 }
40
41 // Inorder to verify BST order after inserts
42 static void inorder(TreeNode node) {
43 if (node == null) return;
44 inorder(node.left);
45 System.out.print(node.val + " ");
46 inorder(node.right);
47 }
48
49 public static void main(String[] args) {
50 TreeNode root = null;
51 int[] values = {8, 3, 10, 1, 6, 14, 4, 7, 13};
52 for (int v : values) root = insertRecursive(root, v);
53
54 System.out.print("Inorder: "); inorder(root); System.out.println();
55 // Inorder: 1 3 4 6 7 8 10 13 14 (sorted ✓)
56
57 root = insertRecursive(root, 5);
58 System.out.print("After inserting 5: "); inorder(root); System.out.println();
59 // 1 3 4 5 6 7 8 10 13 14
60 }
61}Output:
Inorder: 1 3 4 6 7 8 10 13 14
After inserting 5: 1 3 4 5 6 7 8 10 13 14
Operation 3: Delete — Three Cases
Deletion is the most complex BST operation because removing a node must preserve the BST property.
THREE CASES:
CASE 1: Node is a LEAF (no children)
Simply remove it — no restructuring needed.
Delete 7: Delete 7:
6 6
/ \ → /
4 7 4
CASE 2: Node has ONE child
Replace the node with its only child.
Delete 6 (has left child 4 only):
8 8
/ \ → / \
3 10 3 10
/ \ \
6 14 4 ← 6 replaced by child 4
Delete 6 (has right child 7 only):
8 8
/ \ → / \
3 10 3 10
/ \ \
6 14 7 ← 6 replaced by child 7
CASE 3: Node has TWO children
Replace node's value with its INORDER SUCCESSOR
(smallest value in the right subtree = leftmost node in right subtree).
Then delete the inorder successor from the right subtree.
Delete 3 (has children 1 and 6):
8 8
/ \ → / \
3 10 4 10
/ \ / \
1 6 1 6
/ \ / \
4 7 (4 gone) 7
Inorder successor of 3 = 4 (smallest in right subtree {4,6,7})
Replace 3 with 4, then delete original 4.
1public class BSTDelete {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 // Find minimum node (leftmost) in a subtree
9 private static TreeNode findMin(TreeNode node) {
10 while (node.left != null) node = node.left;
11 return node;
12 }
13
14 public static TreeNode delete(TreeNode root, int val) {
15 if (root == null) return null; // Value not found
16
17 if (val < root.val) {
18 root.left = delete(root.left, val); // Search left
19 } else if (val > root.val) {
20 root.right = delete(root.right, val); // Search right
21 } else {
22 // FOUND the node to delete
23 if (root.left == null) return root.right; // Case 1 & 2: no left child
24 if (root.right == null) return root.left; // Case 2: no right child
25
26 // Case 3: two children
27 TreeNode successor = findMin(root.right); // Inorder successor
28 root.val = successor.val; // Replace value
29 root.right = delete(root.right, successor.val); // Delete successor
30 }
31
32 return root;
33 }
34
35 static void inorder(TreeNode node) {
36 if (node == null) return;
37 inorder(node.left);
38 System.out.print(node.val + " ");
39 inorder(node.right);
40 }
41
42 public static void main(String[] args) {
43 // Build BST: 8,3,10,1,6,14,4,7,13
44 TreeNode root = null;
45 for (int v : new int[]{8, 3, 10, 1, 6, 14, 4, 7, 13}) {
46 root = insert(root, v);
47 }
48
49 System.out.print("Before: "); inorder(root); System.out.println();
50 // 1 3 4 6 7 8 10 13 14
51
52 root = delete(root, 3); // Delete node with two children
53 System.out.print("Delete 3: "); inorder(root); System.out.println();
54 // 1 4 6 7 8 10 13 14
55
56 root = delete(root, 14); // Delete node with one child (13)
57 System.out.print("Delete 14: "); inorder(root); System.out.println();
58 // 1 4 6 7 8 10 13
59
60 root = delete(root, 1); // Delete leaf node
61 System.out.print("Delete 1: "); inorder(root); System.out.println();
62 // 4 6 7 8 10 13
63 }
64
65 static TreeNode insert(TreeNode root, int val) {
66 if (root == null) return new TreeNode(val);
67 if (val < root.val) root.left = insert(root.left, val);
68 else if (val > root.val) root.right = insert(root.right, val);
69 return root;
70 }
71}Output:
Before: [1, 3, 4, 6, 7, 8, 10, 13, 14]
Delete 3: [1, 4, 6, 7, 8, 10, 13, 14]
Delete 14: [1, 4, 6, 7, 8, 10, 13]
Delete 1: [4, 6, 7, 8, 10, 13]
Finding Minimum and Maximum
MINIMUM: start at root, keep going LEFT until no left child.
MAXIMUM: start at root, keep going RIGHT until no right child.
8
/ \
3 10
/ \ \
1 6 14
/
13
Minimum: 8 → 3 → 1 (no left child) → MIN = 1
Maximum: 8 → 10 → 14 (no right child) → MAX = 14
1public class BSTMinMax {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 public static int findMin(TreeNode root) {
9 if (root == null) throw new RuntimeException("Empty tree");
10 while (root.left != null) root = root.left;
11 return root.val;
12 }
13
14 public static int findMax(TreeNode root) {
15 if (root == null) throw new RuntimeException("Empty tree");
16 while (root.right != null) root = root.right;
17 return root.val;
18 }
19
20 public static void main(String[] args) {
21 TreeNode root = new TreeNode(8);
22 root.left = new TreeNode(3); root.right = new TreeNode(10);
23 root.left.left = new TreeNode(1); root.left.right = new TreeNode(6);
24 root.right.right = new TreeNode(14);
25 root.right.right.left = new TreeNode(13);
26
27 System.out.println("Min: " + findMin(root)); // 1
28 System.out.println("Max: " + findMax(root)); // 14
29 }
30}Output:
Min: 1
Max: 14
Inorder Successor and Predecessor
Inorder successor of a node: the next node in inorder sequence (next larger value). Inorder predecessor of a node: the previous node in inorder sequence (next smaller value).
BST inorder sequence: 1, 3, 4, 6, 7, 8, 10, 13, 14
Successor of 6 = 7 (next larger in inorder)
Predecessor of 6 = 4 (previous smaller in inorder)
Successor of 14 = null (14 is the largest)
Predecessor of 1 = null (1 is the smallest)
FINDING SUCCESSOR:
Case A: Node has a RIGHT subtree
→ successor = minimum of right subtree
Successor of 3 (right subtree exists): min(right subtree {4,6,7}) = 4 ✓
Case B: Node has NO right subtree
→ successor = deepest ancestor where node is in left subtree
Successor of 7 (no right subtree): go up — 7 is right child of 6,
keep going up — 6 is right child of 3, keep going up — 3 is left child of 8
→ successor = 8 ✓
FINDING PREDECESSOR (mirror):
Case A: Node has a LEFT subtree → max of left subtree
Case B: Node has no left subtree → deepest ancestor where node is in right subtree
1public class InorderSuccessor {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 // In a BST: find inorder successor of a given node
9 public static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
10 TreeNode successor = null;
11
12 while (root != null) {
13 if (p.val < root.val) {
14 // root could be successor — record it and go left (find smaller)
15 successor = root;
16 root = root.left;
17 } else {
18 // p.val >= root.val — successor must be in right subtree
19 root = root.right;
20 }
21 }
22
23 return successor;
24 }
25
26 // Inorder predecessor of a given node
27 public static TreeNode inorderPredecessor(TreeNode root, TreeNode p) {
28 TreeNode predecessor = null;
29
30 while (root != null) {
31 if (p.val > root.val) {
32 // root could be predecessor — record it and go right (find larger)
33 predecessor = root;
34 root = root.right;
35 } else {
36 root = root.left;
37 }
38 }
39
40 return predecessor;
41 }
42
43 public static void main(String[] args) {
44 TreeNode root = new TreeNode(8);
45 root.left = new TreeNode(3); root.right = new TreeNode(10);
46 root.left.left = new TreeNode(1); root.left.right = new TreeNode(6);
47 root.left.right.left = new TreeNode(4);
48 root.left.right.right = new TreeNode(7);
49 root.right.right = new TreeNode(14);
50 root.right.right.left = new TreeNode(13);
51
52 TreeNode p = root.left.right; // Node 6
53 TreeNode succ = inorderSuccessor(root, p);
54 TreeNode pred = inorderPredecessor(root, p);
55
56 System.out.println("Successor of 6: " + (succ != null ? succ.val : "null")); // 7
57 System.out.println("Predecessor of 6: " + (pred != null ? pred.val : "null")); // 4
58 }
59}Output:
Successor of 6: 7
Predecessor of 6: 4
Complexity Summary
| Operation | Average (balanced) | Worst (skewed) | Space |
|---|---|---|---|
| Search | O(log n) | O(n) | O(1) iterative / O(h) recursive |
| Insert | O(log n) | O(n) | O(1) iterative / O(h) recursive |
| Delete | O(log n) | O(n) | O(h) recursive |
| Min / Max | O(log n) | O(n) | O(1) |
| Successor / Predecessor | O(log n) | O(n) | O(1) |
| Inorder traversal | O(n) | O(n) | O(h) |
h = height = O(log n) balanced, O(n) degenerate.
Common Mistakes
Checking only parent-child pairs to validate a BST. The BST property requires ALL ancestors to be satisfied, not just the immediate parent. The classic failing example: a node 6 in the right subtree of 3, but the tree root is 5. 6 > 3 (parent check passes) but 6 > 5 (root constraint violated). Always validate using a [min, max] range passed down recursively.
Using inorder predecessor instead of successor for deletion (or forgetting either works). When deleting a node with two children, both the inorder successor (smallest in right subtree) and inorder predecessor (largest in left subtree) can replace the deleted node. Either choice maintains BST property. The successor approach is slightly more common in textbooks.
Off-by-one in inorder successor search. The successor algorithm uses if (p.val < root.val) — not <=. For duplicate values (if allowed), the successor should be strictly greater. Verify whether your BST allows duplicates and handle accordingly.
Forgetting to return the root from insert/delete. Recursive insert and delete return the (potentially new) root of each subtree. If you call delete(root, val) but forget root = delete(root, val), the tree is not updated. Both insert and delete return root at every level.
Interview Questions
Q: What is the BST property and why must it hold recursively?
For every node N: all values in N's left subtree are strictly less than N.val, and all values in N's right subtree are strictly greater. "Recursively" means this holds at every node simultaneously, not just at the root. If only the immediate parent-child relationship is checked, a node could violate the constraint of a grandparent. The recursive invariant ensures that searching, inserting, and deleting can all follow the single-path rule from root to target.
Q: Why is deletion the most complex BST operation?
Deletion must handle three structural cases. A leaf (no children) is trivial — just remove it. A node with one child is simple — replace it with the child. A node with two children is complex — removing it creates two orphaned subtrees that must be remerged. The solution is to find the inorder successor (smallest in right subtree), replace the deleted node's value with it, and then delete the successor from the right subtree. The successor has at most one child (no left child by definition of minimum), so the second deletion falls into case 1 or 2.
Q: What is the time complexity of BST operations and when is it O(n)?
All core operations (search, insert, delete) are O(h) where h is the tree height. For a balanced BST, h = O(log n), so operations are O(log n). The O(n) worst case occurs when the BST degenerates into a skewed tree — inserting elements in sorted order (1, 2, 3, 4, ...) creates a right-only chain where every node has only a right child. This is why self-balancing trees (AVL, Red-Black) are used in practice — they maintain h = O(log n) after every operation.
Summary
A BST is a binary tree where every node satisfies: left subtree values < node value < right subtree values, recursively.
Three core operations:
- ›Search — follow BST property at each node: go left if target < current, right if target > current. O(h).
- ›Insert — search for insertion point, add new leaf. O(h).
- ›Delete — three cases: leaf (just remove), one child (replace with child), two children (replace with inorder successor, delete successor). O(h).
Two utility operations:
- ›Min — leftmost node. Max — rightmost node. Both O(h).
- ›Inorder successor — smallest value > target: if right subtree exists, min of right subtree; else deepest ancestor where node is in left subtree. O(h).
Inorder traversal always produces sorted ascending output — the fundamental property that enables BST validation, kth-smallest, and floor/ceil queries.
h = O(log n) balanced, O(n) skewed — self-balancing trees (AVL, Red-Black) guarantee O(log n) always.
In the next topic you will explore BST Validation, Floor, Ceil, and Kth Smallest — applying BST operations to classic interview problems.
What is the BST property that must hold at EVERY node?