-
Notifications
You must be signed in to change notification settings - Fork 0
008 — Binary Search Trees
The last chapter gave trees their shape. This chapter adds one rule to that shape, and that one rule is what turns "a bunch of connected nodes" into a structure you can search in O(log n).
Think about your own family tree, but redrawn with a strange, made-up rule: at every person, everyone younger goes in the left seat's descendants, and everyone older goes in the right seat's descendants. Suddenly, if someone asks "is cousin Sam in this family, and how old is he relative to me?" — you don't have to check every branch. You just compare ages and walk left or right, discarding the entire other half of the family at each step.
- 👴 A binary search tree (BST) is a binary tree with an ordering rule baked into every single node.
- 🧭 At any node, everything smaller lives to the left, everything bigger lives to the right — recursively, all the way down.
- ⚡ That rule is what lets you skip half the remaining tree at every step, the same way sorted lockers let you binary search in Chapter 01.
A plain binary tree tells you nothing about where to look. A BST tells you exactly which way to turn.
A binary search tree is a binary tree where, for every node n:
- Every value in
n's left subtree is less thann.value. - Every value in
n's right subtree is greater thann.value. - Both the left and right subtrees are themselves valid BSTs (the rule is recursive, not just "check my direct children").
That single invariant gives you O(log n) search, insert, and delete — but only when the tree stays roughly balanced. Insert values in sorted order into a plain BST (no rebalancing) and it degenerates into a straight line — effectively a linked list wearing a tree costume, and every operation drops to O(n). Self-balancing variants (AVL trees and red-black trees, covered below) solve this by rotating nodes to keep the tree's height near log n no matter what order you insert in — rarely worth hand-rolling in an interview, but worth understanding the mechanics of.
Swift has no stdlib BST — same story as binary trees in general.
Reach for a BST when:
- You need ordered data with fast insert, search, and delete — a sorted array gives you fast search but
O(n)insert/delete; a BST gives youO(log n)(average case) on all three. - You need to repeatedly ask "what's the smallest/largest remaining value," "what's the next value greater/less than X," or walk values in sorted order (an in-order traversal of a BST visits values in ascending order for free).
Skip it when you don't need ordering at all — a hash set beats a BST on every operation if all you need is "is this in the collection," with no ordering requirement.
┌────┐
│ 8 │ ← root
└────┘
/ \
all < 8 / \ all > 8
┌────┐ ┌─────┐
│ 3 │ │ 10 │
└────┘ └─────┘
/ \ \
┌────┐ ┌────┐ ┌────┐
│ 1 │ │ 6 │ │ 14 │
└────┘ └────┘ └────┘
/ \
┌────┐ ┌────┐
│ 4 │ │ 7 │
Searching for 7: 8 → (7 < 8, go left) → 3 → (7 > 3, go right)
→ 6 → (7 > 6, go right) → 7. Found in 3 hops, never touched 1, 10, or 14.
No stdlib equivalent — hand-rolled, generic over any Comparable type.
final class BSTNode<T: Comparable> {
var value: T
var left: BSTNode<T>?
var right: BSTNode<T>?
init(_ value: T) {
self.value = value
}
}
final class BST<T: Comparable> {
private(set) var root: BSTNode<T>?
func insert(_ value: T) {
root = insert(root, value)
}
private func insert(_ node: BSTNode<T>?, _ value: T) -> BSTNode<T> {
guard let node = node else { return BSTNode(value) }
if value < node.value {
node.left = insert(node.left, value)
} else if value > node.value {
node.right = insert(node.right, value)
}
// equal values are ignored — this BST does not allow duplicates
return node
}
func search(_ value: T) -> Bool {
var current = root
while let node = current {
if value == node.value { return true }
current = value < node.value ? node.left : node.right
}
return false
}
func delete(_ value: T) {
root = delete(root, value)
}
private func delete(_ node: BSTNode<T>?, _ value: T) -> BSTNode<T>? {
guard let node = node else { return nil }
if value < node.value {
node.left = delete(node.left, value)
} else if value > node.value {
node.right = delete(node.right, value)
} else {
// found the node to delete
if node.left == nil { return node.right }
if node.right == nil { return node.left }
// two children: replace value with the in-order successor
// (the smallest value in the right subtree), then delete that successor
var successor = node.right!
while let next = successor.left { successor = next }
node.value = successor.value
node.right = delete(node.right, successor.value)
}
return node
}
}Usage:
let tree = BST<Int>()
[8, 3, 10, 1, 6, 14, 4, 7].forEach { tree.insert($0) }
tree.search(6) // true — found by walking right, right? no: 8 → left(3) → right(6)
tree.delete(3) // 3 has two children (1 and 6) — replaced by its in-order successor
tree.search(3) // falseThe search function is written iteratively here (a while loop, not recursion) — that's a deliberate interview habit: it avoids growing the call stack, and BST search doesn't need to backtrack, so there's no reason to pay for recursion.
"In-order" means: for every node, visit left subtree → node itself → right subtree, recursively.
extension BST {
func inOrder() -> [T] {
var result: [T] = []
inOrder(root, &result)
return result
}
private func inOrder(_ node: BSTNode<T>?, _ result: inout [T]) {
guard let node = node else { return }
inOrder(node.left, &result)
result.append(node.value)
inOrder(node.right, &result)
}
}Why does this produce sorted output? Because the ordering rule guarantees everything in the left subtree is smaller than the current node, and everything in the right subtree is bigger. So visiting "all the smaller stuff, then me, then all the bigger stuff" — applied recursively at every level — necessarily walks the values from smallest to largest.
Running this on our example tree gives exactly 1, 3, 4, 6, 7, 8, 10, 14 — the same sorted order the values were in before they got scattered across the tree by insert. This traversal is O(n) (you visit every node once), which makes sense: producing n sorted values can't be faster than O(n).
This is one of the most useful properties of a BST — it's simultaneously a search structure and a way to get a sorted view of your data on demand.
| Operation | Big-O (average) | Big-O (worst case) | Why |
|---|---|---|---|
| Search | O(log n) |
O(n) |
Average case assumes a roughly balanced tree — each comparison discards half the remaining nodes, same shape as binary search. Worst case is a degenerate, linked-list-shaped tree (e.g. inserting already-sorted data). See Big-O Notation. |
| Insert | O(log n) |
O(n) |
Same reasoning as search — insert walks down to find the correct empty spot. |
| Delete | O(log n) |
O(n) |
Also walks down to find the node, plus (for two-child nodes) a walk to find the in-order successor — still bounded by tree height. |
| In-order traversal | O(n) |
O(n) |
Visits every node exactly once, and visits them in sorted order — a free side effect of the ordering rule. |
| Find min / max | O(log n) |
O(n) |
Walk left (min) or right (max) until you hit a nil child — bounded by height. |
The average/worst-case split above is the whole reason self-balancing trees (AVL, red-black) exist: they guarantee O(log n) height no matter the insertion order, at the cost of extra bookkeeping on every insert/delete.
An AVL tree is a BST with one extra invariant enforced at every node: the heights of its left and right subtrees may differ by at most 1. Track a balance factor (height(left) - height(right)) at each node; the moment an insert pushes it to 2 or -2, rotate to bring it back into [-1, 1] before returning up the call stack. Because the fix happens immediately at every level, the tree never gets to become a straight line — height stays within roughly 1.44 * log₂(n) of minimum, always.
There are exactly four imbalance shapes, and each has a standard fix:
- Left-Left (inserted into the left subtree's left subtree) → one right rotation.
- Right-Right (mirror of LL) → one left rotation.
- Left-Right (inserted into the left subtree's right subtree) → rotate the left child left, then rotate the node right.
- Right-Left (mirror of LR) → rotate the right child right, then rotate the node left.
Left-Left case, fixed by a single right rotation around z:
z y
/ \ / \
y T4 ──────► x z
/ \ / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
final class AVLNode<T: Comparable> {
var value: T
var left: AVLNode<T>?
var right: AVLNode<T>?
var height = 1
init(_ value: T) {
self.value = value
}
}
final class AVLTree<T: Comparable> {
private(set) var root: AVLNode<T>?
func insert(_ value: T) {
root = insert(root, value)
}
private func insert(_ node: AVLNode<T>?, _ value: T) -> AVLNode<T> {
guard let node = node else { return AVLNode(value) }
if value < node.value {
node.left = insert(node.left, value)
} else if value > node.value {
node.right = insert(node.right, value)
} else {
return node // no duplicates
}
return rebalance(node)
}
private func height(_ node: AVLNode<T>?) -> Int {
node?.height ?? 0
}
private func balanceFactor(_ node: AVLNode<T>) -> Int {
height(node.left) - height(node.right)
}
private func rebalance(_ node: AVLNode<T>) -> AVLNode<T> {
node.height = 1 + max(height(node.left), height(node.right))
let balance = balanceFactor(node)
if balance > 1 {
if balanceFactor(node.left!) < 0 {
node.left = rotateLeft(node.left!) // left-right case
}
return rotateRight(node) // left-left case
}
if balance < -1 {
if balanceFactor(node.right!) > 0 {
node.right = rotateRight(node.right!) // right-left case
}
return rotateLeft(node) // right-right case
}
return node
}
private func rotateRight(_ y: AVLNode<T>) -> AVLNode<T> {
let x = y.left!
y.left = x.right
x.right = y
y.height = 1 + max(height(y.left), height(y.right))
x.height = 1 + max(height(x.left), height(x.right))
return x
}
private func rotateLeft(_ x: AVLNode<T>) -> AVLNode<T> {
let y = x.right!
x.right = y.left
y.left = x
x.height = 1 + max(height(x.left), height(x.right))
y.height = 1 + max(height(y.left), height(y.right))
return y
}
}delete isn't shown here — it's the same idea, not new code to learn: run the ordinary BST delete, then call rebalance on every ancestor on the way back up, exactly like insert already does. The rotation logic doesn't change; only which node you're reacting to does.
Because rebalancing happens on every insert and delete, AVL trees give you O(log n) worst case for search, insert, and delete — not just average case, unlike a plain BST.
A red-black tree trades some of AVL's strictness for cheaper rebalancing. Instead of tracking exact heights, each node gets a color — red or black — and the tree maintains three rules:
- The root is always black.
- A red node never has a red child (no two reds in a row along any path).
- Every path from a node down to a
nilleaf passes through the same number of black nodes (the black-height).
Those rules bound the height at roughly 2 * log₂(n+1) — looser than AVL's bound, so red-black trees allow slightly deeper trees and slightly slower lookups. What they buy back is cheaper writes: fixing a violation after insert takes at most a couple of rotations plus some recoloring, versus AVL's rebalance-every-ancestor-on-the-way-up. That's why red-black trees (not AVL) back C++'s std::map/std::set and Java's TreeMap/TreeSet — those workloads are write-heavy enough that cheaper inserts/deletes outweigh AVL's tighter lookups.
The implementation below is Sedgewick's left-leaning red-black tree (LLRB) — a well-known simplification that gets the same O(log n) guarantees with far less code, by adding one more rule ("red links always lean left") that collapses the classic 2-3-4 tree cases into just three checks:
final class RBNode<T: Comparable> {
var value: T
var left: RBNode<T>?
var right: RBNode<T>?
var isRed = true // new nodes are always inserted red
init(_ value: T) {
self.value = value
}
}
final class RedBlackTree<T: Comparable> {
private(set) var root: RBNode<T>?
func insert(_ value: T) {
root = insert(root, value)
root?.isRed = false // root is always black
}
private func insert(_ node: RBNode<T>?, _ value: T) -> RBNode<T> {
guard let node = node else { return RBNode(value) }
var h = node
if value < h.value {
h.left = insert(h.left, value)
} else if value > h.value {
h.right = insert(h.right, value)
}
// equal values ignored — no duplicates
if isRed(h.right) && !isRed(h.left) {
h = rotateLeft(h) // lean red links left
}
if isRed(h.left) && isRed(h.left?.left) {
h = rotateRight(h) // break up two reds in a row
}
if isRed(h.left) && isRed(h.right) {
flipColors(h) // push a red up instead of rotating further
}
return h
}
private func isRed(_ node: RBNode<T>?) -> Bool {
node?.isRed ?? false
}
private func rotateLeft(_ h: RBNode<T>) -> RBNode<T> {
let x = h.right!
h.right = x.left
x.left = h
x.isRed = h.isRed
h.isRed = true
return x
}
private func rotateRight(_ h: RBNode<T>) -> RBNode<T> {
let x = h.left!
h.left = x.right
x.right = h
x.isRed = h.isRed
h.isRed = true
return x
}
private func flipColors(_ h: RBNode<T>) {
h.isRed.toggle()
h.left?.isRed.toggle()
h.right?.isRed.toggle()
}
}As with AVL, delete reuses the same three checks — it just also has to handle temporarily borrowing a red link from a sibling before removing a node, which is where most of red-black delete's reputation for complexity comes from. Worth knowing it exists; rarely worth hand-writing outside of implementing a language's standard library.
AVL vs. red-black, at a glance:
| AVL | Red-Black | |
|---|---|---|
| Balance guarantee | Tighter (~1.44 log n) |
Looser (~2 log n) |
| Lookups | Slightly faster | Slightly slower |
| Insert/delete | More rotations | Fewer rotations, more recoloring |
| Typical use | Read-heavy structures (e.g. database indexes) | Write-heavy structures (e.g. std::map, TreeMap) |
A binary search tree is a binary tree with one extra rule — smaller goes left, bigger goes right, always — and that one rule is what lets you throw away half the tree with every comparison.
If you insert the values 1, 2, 3, 4, 5 (already sorted) into an empty BST one at a time using the insert function above, draw the resulting shape. What is its height, what does that make search's Big-O for this particular tree, and what real-world insertion pattern would you need to guard against to avoid this happening in production code?
⬅️ Previous: Binary Trees · Next: Heaps & Priority Queues ➡️