Binary Search Trees
The BST ordering invariant, every core operation including the three deletion cases, successor/floor/ceiling queries, and why an unbalanced BST can degrade to a linked list.
What you will learn
The BST ordering invariant, every core operation including the three deletion cases, successor/floor/ceiling queries, and why an unbalanced BST can degrade to a linked list.
Prerequisites: Module 11.
BST property
For a chosen duplicate policy, keys in the left subtree obey the lower-key rule and keys in the right subtree obey the higher-key rule. State the duplicate policy explicitly.
This module uses distinct keys: inserting an existing key does nothing. (Alternatives: store a count per node, or send equal keys consistently to one side.)
Operations
Search, insert, delete (leaf, one child, two children), minimum/maximum, predecessor/successor, floor/ceil, range query, and inorder sorted traversal.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Deleting a node with two children replaces its key with its inorder successor (the minimum of the right subtree, which has no left child) and then deletes that successor — one of the two easy cases.
#include <bits/stdc++.h>
using namespace std;
struct Node { int key; Node* left = nullptr; Node* right = nullptr; explicit Node(int k) : key(k) {} };
Node* insert(Node* n, int k) {
if (!n) return new Node(k);
if (k < n->key) n->left = insert(n->left, k);
else if (k > n->key) n->right = insert(n->right, k); // equal: ignored (distinct-key policy)
return n;
}
Node* minNode(Node* n) { while (n->left) n = n->left; return n; }
Node* erase(Node* n, int k) {
if (!n) return nullptr;
if (k < n->key) n->left = erase(n->left, k);
else if (k > n->key) n->right = erase(n->right, k);
else if (!n->left || !n->right) { // leaf or one child: splice out
Node* child = n->left ? n->left : n->right;
delete n;
return child;
} else { // two children: copy successor, delete it
Node* s = minNode(n->right);
n->key = s->key;
n->right = erase(n->right, s->key);
}
return n;
}
const Node* floorNode(const Node* n, int k) { // largest key <= k
const Node* best = nullptr;
while (n) { if (n->key == k) return n; if (n->key < k)
…inorder: 20 30 35 40 45 50 60 65 70 80 (height 3)
floor(42)=40 ceil(42)=45 floor(10)=none
keys in [33, 62]: 35 40 45 50 60
erase leaf 20 : 30 35 40 45 50 60 65 70 80
erase one-child 60 : 30 35 40 45 50 65 70 80 (65 moves up)
erase two-child 50 : 30 35 40 45 65 70 80 (new root 65 = old successor)
1000 sorted inserts -> height 999 (a linked list)
1000 shuffled inserts -> height 22 (log2 1000 is about 10)Complexity
Average O(log n) when reasonably balanced; worst-case O(n) for a skewed tree.
The run confirms it: 1000 sorted insertions produced height 999; 1000 shuffled insertions gave a height in the low twenties (the expected height of a random BST is about 4.3 ln n, while log₂ 1000 ≈ 10 is the best possible).
Advanced BST topics
Order-statistic trees, rank/select, subtree size augmentation, interval trees, randomized treaps, and why balanced BSTs are needed for guaranteed logarithmic operations.
Augmenting each node with its subtree size lets you answer rank(k) (how many keys are smaller) and select(i) (the i-th smallest) in O(h): walk down, adding the left subtree's size whenever you go right. Every augmentation must be updated on insert, delete and rotation.
Practice
Easy: validate a BST (pass (low, high) bounds down; comparing only with direct children is wrong).
Medium: kth smallest element using an iterative inorder traversal.
Hard: convert a sorted array into a height-balanced BST and prove the height bound.
Quiz
? Deleting a node with two children: which key replaces it?
+ Its inorder successor (minimum of the right subtree) — or the predecessor, consistently :: Keeps the BST order.
- Its left child :: Can break the order.
- The root :: No.
- Any leaf :: Breaks the order.
? 1000 keys inserted in sorted order give height 999. Why?
+ Each new key is larger than all others, so it always goes to the far right — the tree degenerates into a list. :: Balanced trees (Module 13) prevent this.
- A bug in insert. :: Expected behaviour.
- Duplicates. :: All keys were distinct.
- The keys were too large. :: Values do not matter, only order.
? Why is checking `left->key < node->key < right->key` at each node not enough to validate a BST?
+ A deeper node can violate an ancestor's bound (e.g. a 6 in the left subtree of 5). :: Pass min/max bounds down.
- It is enough. :: It misses non-local violations.
- It rejects valid trees. :: It accepts invalid ones.
- It only fails for duplicates. :: Fails without duplicates too.