Binary search tree¶
A tree where everything in a node's left branch is smaller than it and everything in its right branch is larger. Searching is a walk from the root: go left or right at each node, like binary search, but the data can change.
| Search / insert / delete | Worst case (unbalanced) | In-order walk | Extra space |
|---|---|---|---|
| \(O(h)\); \(O(\log n)\) when balanced | \(O(n)\) (a tree that is a line) | \(O(n)\), in sorted order | one node per key |
The idea¶
A sorted array gives \(O(\log n)\) search but \(O(n)\) insertion (everything must shift). A linked list gives \(O(1)\) insertion but \(O(n)\) search. A binary search tree (BST) gets the best of both, provided it stays bushy.
Each node holds a key and up to two children. The BST rule: every key in the left subtree is smaller, every key in the right subtree is larger. So:
- Search: at each node, stop if equal; go left if the key is smaller, right if larger.
- Insert: search for the key; where the search falls off the tree, hang a new node.
- Delete: a leaf just goes; a node with one child is replaced by that child; a node with two children takes the key of its successor (the smallest key in its right subtree), which is then deleted from there.
- In-order walk (left subtree, node, right subtree) lists the keys in sorted order.
Everything costs \(O(h)\) where \(h\) is the height. Random insertions keep \(h\) around \(2\ln n\), but inserting keys
in sorted order builds a line with \(h = n\). Self-balancing trees (AVL, red-black) fix this by rotating
nodes after each change, guaranteeing \(h = O(\log n)\). Java's TreeMap and C++'s std::map are red-black trees.
How it works¶
insert(node, k): empty → new node;k < node.key→ insert left;k > node.key→ insert right.delete(node, k): find it; 0 or 1 child → return the other child; 2 children → copy the successor's key in and delete the successor from the right subtree.
Code¶
class Node:
def __init__(self, key):
self.key = key
self.left = None # keys smaller than this one
self.right = None # keys larger than this one
def insert(root, key):
"""Inserts key (if new) and returns the root of the tree."""
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root
def contains(root, key):
while root is not None: # go left or right, like a binary search
if key == root.key:
return True
root = root.left if key < root.key else root.right
return False
def delete(root, key):
"""Removes key (if present) and returns the root of the tree."""
if root is None:
return None
if key < root.key:
root.left = delete(root.left, key)
elif key > root.key:
root.right = delete(root.right, key)
else:
if root.left is None: # zero or one child: lift the child up
return root.right
if root.right is None:
return root.left
succ = root.right # two children: copy in the next larger key ...
while succ.left is not None:
succ = succ.left
root.key = succ.key
root.right = delete(root.right, succ.key) # ... and delete it from the right subtree
return root
def inorder(root, out):
"""Left subtree, node, right subtree: visits the keys in sorted order."""
if root is not None:
inorder(root.left, out)
out.append(root.key)
inorder(root.right, out)
return out
def height(root):
return 0 if root is None else 1 + max(height(root.left), height(root.right))
if __name__ == "__main__":
root = None
for k in [50, 30, 70, 20, 40, 60, 80, 35]:
root = insert(root, k)
print(inorder(root, []), height(root))
print(contains(root, 60), contains(root, 65))
for k in [20, 30, 50]: # a leaf, a node with two children, the root
root = delete(root, k)
print(inorder(root, []), "root", root.key)
chain = None
for k in range(1, 8): # sorted input makes a tall, thin tree
chain = insert(chain, k)
print("height after inserting 1..7 in order:", height(chain))
import java.util.ArrayList;
import java.util.List;
public class Bst {
static class Node {
int key;
Node left, right; // smaller keys on the left, larger on the right
Node(int key) { this.key = key; }
}
/** Inserts key (if new) and returns the root of the tree. */
static Node insert(Node root, int key) {
if (root == null) return new Node(key);
if (key < root.key) root.left = insert(root.left, key);
else if (key > root.key) root.right = insert(root.right, key);
return root;
}
static boolean contains(Node root, int key) {
while (root != null) { // go left or right, like a binary search
if (key == root.key) return true;
root = key < root.key ? root.left : root.right;
}
return false;
}
/** Removes key (if present) and returns the root of the tree. */
static Node delete(Node root, int key) {
if (root == null) return null;
if (key < root.key) root.left = delete(root.left, key);
else if (key > root.key) root.right = delete(root.right, key);
else {
if (root.left == null) return root.right; // zero or one child: lift the child up
if (root.right == null) return root.left;
Node succ = root.right; // two children: copy in the next larger key ...
while (succ.left != null) succ = succ.left;
root.key = succ.key;
root.right = delete(root.right, succ.key); // ... and delete it from the right subtree
}
return root;
}
/** Left subtree, node, right subtree: visits the keys in sorted order. */
static List<Integer> inorder(Node root, List<Integer> out) {
if (root != null) { inorder(root.left, out); out.add(root.key); inorder(root.right, out); }
return out;
}
static int height(Node root) { return root == null ? 0 : 1 + Math.max(height(root.left), height(root.right)); }
public static void main(String[] args) {
Node root = null;
for (int k : new int[]{50, 30, 70, 20, 40, 60, 80, 35}) root = insert(root, k);
System.out.println(inorder(root, new ArrayList<>()) + " " + height(root));
System.out.println((contains(root, 60) ? "True" : "False") + " " + (contains(root, 65) ? "True" : "False"));
for (int k : new int[]{20, 30, 50}) { // a leaf, a node with two children, the root
root = delete(root, k);
System.out.println(inorder(root, new ArrayList<>()) + " root " + root.key);
}
Node chain = null;
for (int k = 1; k <= 7; k++) chain = insert(chain, k); // sorted input makes a tall, thin tree
System.out.println("height after inserting 1..7 in order: " + height(chain));
}
}
#include <algorithm>
#include <iostream>
#include <memory>
#include <vector>
using namespace std;
struct Node {
int key;
unique_ptr<Node> left, right; // smaller keys on the left, larger on the right
explicit Node(int k) : key(k) {}
};
using Tree = unique_ptr<Node>;
// Inserts key (if new) into the tree.
void insert(Tree& root, int key) {
if (!root) { root = make_unique<Node>(key); return; }
if (key < root->key) insert(root->left, key);
else if (key > root->key) insert(root->right, key);
}
bool contains(const Node* root, int key) {
while (root) { // go left or right, like a binary search
if (key == root->key) return true;
root = key < root->key ? root->left.get() : root->right.get();
}
return false;
}
// Removes key (if present) from the tree.
void erase(Tree& root, int key) {
if (!root) return;
if (key < root->key) erase(root->left, key);
else if (key > root->key) erase(root->right, key);
else if (!root->left) root = std::move(root->right); // zero or one child: lift the child up
else if (!root->right) root = std::move(root->left);
else {
Node* succ = root->right.get(); // two children: copy in the next larger key ...
while (succ->left) succ = succ->left.get();
root->key = succ->key;
erase(root->right, succ->key); // ... and delete it from the right subtree
}
}
// Left subtree, node, right subtree: visits the keys in sorted order.
void inorder(const Node* root, vector<int>& out) {
if (!root) return;
inorder(root->left.get(), out);
out.push_back(root->key);
inorder(root->right.get(), out);
}
int height(const Node* root) { return root ? 1 + max(height(root->left.get()), height(root->right.get())) : 0; }
void print(const Tree& root) {
vector<int> v;
inorder(root.get(), v);
cout << "[";
for (size_t i = 0; i < v.size(); i++) cout << (i ? ", " : "") << v[i];
cout << "]";
}
int main() {
Tree root;
for (int k : {50, 30, 70, 20, 40, 60, 80, 35}) insert(root, k);
print(root);
cout << " " << height(root.get()) << "\n";
cout << (contains(root.get(), 60) ? "True" : "False") << " " << (contains(root.get(), 65) ? "True" : "False") << "\n";
for (int k : {20, 30, 50}) { // a leaf, a node with two children, the root
erase(root, k);
print(root);
cout << " root " << root->key << "\n";
}
Tree chain;
for (int k = 1; k <= 7; k++) insert(chain, k); // sorted input makes a tall, thin tree
cout << "height after inserting 1..7 in order: " << height(chain.get()) << "\n";
}
Output: the in-order walk [20, 30, 35, 40, 50, 60, 70, 80] with height 4; True False for 60 and 65; three
deletions (a leaf, a node with two children, then the root, whose place 60 takes); and a height of 7 when
1..7 are inserted in order: the tree has become a list.
When to use it¶
- Ordered data that changes: a leaderboard, an order book, a calendar of events.
- Queries a hash table cannot answer: the smallest key \(\ge x\) (
ceiling,lower_bound), the keys in a range, the \(k\)-th smallest (with subtree sizes stored). - In practice, use the library's balanced tree (
TreeMap,std::map,std::set; in Python, thesortedcontainerspackage orbisecton a list for small data).
Common mistakes¶
- Sorted input into a plain BST: the tree degenerates into a list, and everything becomes \(O(n)\).
- Forgetting to return the (possibly new) root from
insertanddelete, so the change is lost. - Duplicates: decide whether they are ignored (as here), counted, or always sent one way.
- Recursion depth on a degenerate tree of \(10^5\) nodes overflows the stack.
Going deeper¶
Each part below starts closed; open the ones you want.
Sample walkthrough: insert 50, 30, 70, 20, 40, 60, 80, 35, then delete 30
50
/ \
30 70
/ \ / \
20 40 60 80
/
35
Delete 30 (two children): its successor is the smallest key in its right subtree, 35. Copy 35 into 30's node, then delete the old 35 (a leaf):
50
/ \
35 70
/ \ / \
20 40 60 80
The math: height, and why random trees are shallow
Height bounds. A binary tree of height \(h\) holds at most \(2^h - 1\) nodes, so \(h \ge \lceil \log_2(n+1) \rceil\). A chain has \(h = n\). So \(\log_2 n \lesssim h \le n\).
Random insertion order. If the \(n\) keys arrive in a uniformly random order, the expected depth of a node is \(2 \ln n + O(1) \approx 1.39 \log_2 n\), and the expected height is about \(4.311 \ln n\) (Devroye, 1986). The proof mirrors quicksort: keys \(i < j\) are in an ancestor relationship exactly when one of them is inserted first among the keys \(i, \ldots, j\), which happens with probability \(\frac{2}{j - i + 1}\), so the total depth is
AVL trees keep the heights of every node's two subtrees within 1 of each other. The fewest nodes in an AVL tree of height \(h\) satisfies \(N(h) = N(h-1) + N(h-2) + 1\), a Fibonacci recurrence, so \(N(h) \ge \varphi^{h} / \sqrt5 - 1\) and
Red-black trees colour nodes so that no red node has a red child and every root-to-leaf path has the same number of black nodes; this gives \(h \le 2 \log_2(n + 1)\).
Watch it step by step
Orange nodes are compared on the way down; blue is the new node.
Variations and related ideas
- AVL trees (Adelson-Velsky and Landis, 1962) and red-black trees (Bayer 1972; Guibas and Sedgewick 1978): rotations keep them balanced.
- Treaps give each node a random priority and keep them in heap order: balanced with high probability.
- Splay trees move every accessed node to the root: \(O(\log n)\) amortized, and fast for repeated access.
- B-trees have many keys per node, so a lookup reads few disk blocks; every database index and file system uses them.
- Order statistics: store subtree sizes to find the \(k\)-th smallest key, or a key's rank, in \(O(h)\).
See also¶
- Binary search: the same idea on a static array
- Hash table: faster for exact look-ups, but unordered
- Binary heap: a weaker order that is cheaper to keep
References¶
- T. H. Cormen et al., Introduction to Algorithms, 4th ed., Chapter 12 (binary search trees) and Chapter 13 (red-black trees).
- G. M. Adelson-Velsky, E. M. Landis, "An algorithm for the organization of information", Soviet Mathematics Doklady 3, 1962.
- L. Devroye, "A note on the height of binary search trees", Journal of the ACM 33(3), 1986.