Binary Search Trees
A binary search tree (BST) is a binary tree whose keys obey one rule: for every node, every key in its left subtree is smaller than the node's key and every key in its right subtree is larger. That invariant turns a pointer structure into a sorted dictionary: find, insert, delete, and ordered questions ("largest key not above 42?", "7th smallest?") each walk one root-to-leaf path, costing for height .
The catch is in that . A BST built from shuffled keys has height around in the limit and average depth around , which is excellent. A BST built from sorted keys is a linked list with height , which is a disaster. This lesson builds every operation from first principles, proves each keeps the invariant, quantifies when the tree is fast, and ends at the ordered maps your language ships. The next lesson, Balanced BSTs: AVL & Red-Black Trees, removes the catch.
Why this exists
Binary search on a sorted array answers "is present?" in comparisons, which is optimal for comparison-based search. Its weakness is updates: inserting into the middle of a sorted array shifts up to elements. A hash table fixes updates but throws away order. The BST keeps both: binary-search-like queries, and updates because only pointers change.
The idea appeared independently around 1960, credited to P. F. Windley, A. D. Booth, A. Colin and T. N. Hibbard among others. Hibbard's 1962 paper "Some combinatorial properties of certain trees with applications to searching and sorting" (Journal of the ACM 9(1)) analysed the average cost of search in a randomly built tree and gave the deletion algorithm still taught today (replace a two-child node by its successor), which is why it is often called Hibbard deletion.
You will rarely ship a plain BST. You will constantly ship its descendants: the red-black tree inside Java's TreeMap and C++'s std::map, the B+-tree inside every relational database index (see Indexing Deep Dive), the treap and the skip list in the lesson after next. Each is a BST plus a rule that keeps the height logarithmic, and each runs this page's search, successor, floor, rank and range algorithms unchanged.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "binary search tree", "BST" in the statement | Use the invariant: prune half the tree at every node, and inorder is sorted |
| "validate", "is this a valid BST" | Min/max bounds passed down, or inorder with a prev value |
| "k-th smallest / largest" in a BST | Inorder with early stop, or size-augmented nodes for |
| "inorder successor / predecessor", "next larger key" | Right-subtree minimum, or "last node where we went left" |
| "closest value", "floor", "ceiling", "largest key ≤ x" | One root-to-leaf walk keeping the best candidate |
| "sum / count of keys in [lo, hi]" | Range traversal that skips subtrees outside the interval |
| "convert sorted array / list to a height-balanced BST" | Middle element as root, recurse on halves |
| "two nodes were swapped by mistake" | Inorder has one or two inversions; fix them |
"iterator over a BST with next() and hasNext()" | Controlled inorder with an explicit stack, memory |
| "maintain a sorted set under inserts and deletes and ask neighbours" | Ordered map: TreeMap, std::set, SortedList |
| "count elements smaller than x seen so far", "rank in a stream" | Order-statistic tree (size-augmented BST) or a Fenwick tree |
| "lowest common ancestor" in a BST | First node where the two keys split left and right |
The common signal is order plus change: static data wants a sorted array with binary search, pure membership wants a hash table.
Intuition & first principles
The invariant
Take a node with key . The BST property says:
Note the quantifier: every key in the subtree, not just the child. Checking only children is not enough; that misreading is the most common BST bug, met again in validation.
This page assumes distinct keys. Duplicates are handled by one of three conventions, chosen once and applied everywhere: reject them (sets and maps do this), store a count in the node (multisets), or send equal keys consistently to one side (for example < goes left, >= goes right). The third convention complicates deletion and validation, which is why libraries prefer the first two.
Why the invariant is a search algorithm
Standing at a node with key while looking for , the invariant gives three outcomes: (found), (if is anywhere, it is in the left subtree, because every right-subtree key exceeds ), or (symmetrically, right subtree). One comparison discards the node and an entire subtree. That is binary search, except that the "middle" is wherever the tree happens to put the root, and the halves can be badly unequal.
Think of a BST as a sorted array folded into a decision tree whose comparison points were fixed at insertion time: random insertion order puts them near the middle on average; sorted order puts every one at the edge, and binary search becomes linear search.
The inorder-sorted lemma
Lemma. An inorder traversal (left subtree, node, right subtree) of a BST visits the keys in strictly increasing order. Conversely, a binary tree whose inorder sequence is strictly increasing is a BST.
Proof by strong induction on the number of nodes . For the sequence is empty and trivially sorted. For , let the root have key . Inorder emits , then , then . Both subtrees are BSTs with fewer nodes, so by the induction hypothesis each emits its keys in increasing order. Every key of is less than and every key of is greater than by the BST property, so the concatenation is increasing.
For the converse, suppose the inorder sequence is strictly increasing. Every key of appears before in the sequence, so it is smaller than ; every key of appears after , so it is larger. That is the BST property at the root; apply the same argument to every subtree (the inorder sequence of a subtree is a contiguous piece of the whole sequence, so it is increasing too). ∎
This lemma is the single most useful fact on this page. It gives you validation (check the inorder sequence is increasing), k-th smallest (the k-th element of inorder), recovery of swapped nodes (find the inversions in inorder), iteration in sorted order, and the reduction of "convert a sorted array to a BST" to "pick a root, recurse". When a BST problem feels hard, ask what it means for the inorder sequence.
Height is everything
Every operation below walks one path from the root, so it costs comparisons, where is the height (number of edges on the longest root-to-leaf path; an empty tree has height , a single node height ). A binary tree with nodes satisfies
The lower bound holds because a tree of height has at most nodes; the upper bound is the chain. For that is 19 versus 999,999. The shape is decided entirely by the order in which keys were inserted (and deleted), which is why balanced trees exist.
Mechanics
All traces below use the tree built by inserting 50, 30, 70, 20, 40, 60, 80, 35, 45, 65 in that order. Every value in the traces was produced by running the code in this lesson.
flowchart TD
N50["50"] --> N30["30"]
N50 --> N70["70"]
N30 --> N20["20"]
N30 --> N40["40"]
N40 --> N35["35"]
N40 --> N45["45"]
N70 --> N60["60"]
N70 --> N80["80"]
N60 --> X1["(empty)"]
N60 --> N65["65"]
Its inorder sequence is 20 30 35 40 45 50 60 65 70 80, its height is 3, and subtree sizes are 50:10, 30:5, 70:4, 40:3, 60:2, all other nodes 1.
Search
Start at the root. Compare, then go left, go right, or stop.
Trace: search for 65, then for 42.
| Step | Target | Node | Comparison | Next |
|---|---|---|---|---|
| 1 | 65 | 50 | 65 > 50 | right |
| 2 | 65 | 70 | 65 < 70 | left |
| 3 | 65 | 60 | 65 > 60 | right |
| 4 | 65 | 65 | equal | found after 4 comparisons |
| 1 | 42 | 50 | 42 < 50 | left |
| 2 | 42 | 30 | 42 > 30 | right |
| 3 | 42 | 40 | 42 > 40 | right |
| 4 | 42 | 45 | 42 < 45 | left child is empty: not found |
An unsuccessful search ends at an empty child pointer. That position is exactly where the key would be, which is the whole idea behind insertion.
Insert
Search for the key; when you fall off the tree at an empty child, hang a new leaf there. Inserting 42 follows the second half of the trace above and attaches 42 as the left child of 45. The tree's height grows from 3 to 4. Insertion never moves an existing node, so iterators stay valid.
Why the property survives. The new leaf hangs below a path . At each we went left exactly when , so lands in 's left subtree only if it is smaller than and in the right subtree only if it is larger. No other node's subtree changes. So every ancestor's constraint holds, and no other constraint is touched.
Delete: three cases
Deletion is the operation people get wrong, because removing a node with two children leaves two subtrees that both need a parent.
flowchart TD
S["find node z with key x"] --> Q{"how many children?"}
Q -->|"0"| C1["Case 1: leaf<br/>replace z by empty"]
Q -->|"1"| C2["Case 2: one child<br/>splice z out, child takes its place"]
Q -->|"2"| C3["Case 3: two children"]
C3 --> F["s = minimum of z.right<br/>(inorder successor, has no left child)"]
F --> CP["copy s.key into z"]
CP --> DS["delete s from z.right<br/>(now Case 1 or Case 2)"]
- Case 1, leaf. Remove it: the parent's pointer becomes empty.
- Case 2, one child. Splice it out: the parent's pointer now points to the only child.
- Case 3, two children. Find the inorder successor , the minimum of the right subtree (go right once, then left until you cannot). Copy 's key (and value) into , then delete from the right subtree. Because is a minimum, it has no left child, so that second deletion is Case 1 or 2 and the recursion stops after one level. The predecessor (maximum of the left subtree) works equally well.
Trace: deleting 20, then 60, then 50 (on the original tree).
| Step | Delete | Node found | Case | Action | Inorder afterwards |
|---|---|---|---|---|---|
| 1 | 20 | leaf under 30 | 1 | 30.left = empty | 30 35 40 45 50 60 65 70 80 |
| 2 | 60 | only right child 65 | 2 | 70.left = 65 | 30 35 40 45 50 65 70 80 |
| 3 | 50 | root, children 30 and 70 | 3 | successor: right to 70, left to 65, 65.left empty, so s = 65 | |
| 4 | copy 65 into root; delete 65 from right subtree (leaf, Case 1) | 30 35 40 45 65 70 80 |
The final tree is 65(30(., 40(35, 45)), 70(., 80)). On the original tree, deleting 50 directly finds successor 60, which has a right child, so Case 3 falls through to Case 2: 60(30(20, 40(35, 45)), 70(65, 80)).
Proof that Case 3 keeps the BST property. Let have key , left subtree , right subtree , and let .
- Every key in is , so is still a valid left subtree of a node holding .
- Every key in is , because was the minimum of and keys are distinct. So with removed is a valid right subtree of a node holding .
- Ancestors of : 's position relative to each ancestor was decided by ; since , lies on the same side of as does (all of 's subtree did). So 's constraint still holds.
- Removing from is Case 1 or 2 (no left child), and removing a node with at most one child keeps the property: the child's subtree was already on the correct side of every ancestor of .
Cases 1 and 2 are the same argument as step 4. ∎
Successor and predecessor
The successor of is the smallest key greater than . Two settings:
With parent pointers, starting from node (what iterators in std::map and TreeMap do):
flowchart TD
A["node v"] --> Q{"v has a right child?"}
Q -->|"yes"| B["successor = leftmost node of v.right"]
Q -->|"no"| C["climb: while v is a right child,<br/>v = v.parent"]
C --> D["successor = v.parent<br/>(empty if we reached the root)"]
The second branch says: if has no right subtree, its successor is the nearest ancestor of which lies in the left subtree. Every ancestor we climb through while coming up from the right is smaller than , so it cannot be the successor.
from __future__ import annotations
from dataclasses import dataclass
from typing import Optional
@dataclass(eq=False)
class PNode:
key: int
left: Optional[PNode] = None
right: Optional[PNode] = None
parent: Optional[PNode] = None
def insert(root: Optional[PNode], key: int) -> PNode:
node = PNode(key)
if root is None:
return node
cur = root
while True:
if key < cur.key:
if cur.left is None:
cur.left, node.parent = node, cur
return root
cur = cur.left
else:
if cur.right is None:
cur.right, node.parent = node, cur
return root
cur = cur.right
def find(root: Optional[PNode], key: int) -> Optional[PNode]:
while root and root.key != key:
root = root.left if key < root.key else root.right
return root
def successor(v: PNode) -> Optional[PNode]:
if v.right: # leftmost node of the right subtree
v = v.right
while v.left:
v = v.left
return v
while v.parent and v is v.parent.right: # climb while we are a right child
v = v.parent
return v.parent
root = None
for k in [50, 30, 70, 20, 40, 60, 80, 35, 45, 65]:
root = insert(root, k)
order, v = [], find(root, 20)
while v: # walk the whole tree with successor()
order.append(v.key)
v = successor(v)
assert order == [20, 30, 35, 40, 45, 50, 60, 65, 70, 80]
assert successor(find(root, 45)).key == 50 # climb case
assert successor(find(root, 60)).key == 65 # right-subtree case
assert successor(find(root, 80)) is None
Walking the entire tree by repeated successor costs total, not , because each edge is traversed at most twice (once down, once up). That is why an ordered-map iterator's ++ is amortized and worst case.
Without parent pointers, from the root, given a key . Walk down as if searching for . Every time you go left from a node, that node is larger than and is a candidate; remember the most recent one. When the walk ends, the last remembered candidate is the successor. This works even if is not in the tree.
Trace: successor(40) without parent pointers.
| Step | Node | Compare | Candidate | Move |
|---|---|---|---|---|
| 1 | 50 | 40 < 50 | 50 | left |
| 2 | 30 | 40 ≥ 30 | 50 | right |
| 3 | 40 | 40 ≥ 40 | 50 | right |
| 4 | 45 | 40 < 45 | 45 | left, empty: stop |
Answer 45. For successor(45) the walk goes left at 50, then right at 30, 40 and 45, so the answer stays 50; for successor(80) it never goes left, so there is none. Predecessor is the mirror image: remember the node each time you go right.
Floor and ceiling
Floor is the largest key ; ceiling is the smallest key . Same walk, same idea, with equality short-circuiting.
Trace: floor and ceiling of 42 and of 63 (computed together: going right records a floor candidate, going left records a ceiling candidate).
| x | Node | Relation | Floor so far | Ceiling so far | Move |
|---|---|---|---|---|---|
| 42 | 50 | 50 > 42 | – | 50 | left |
| 42 | 30 | 30 < 42 | 30 | 50 | right |
| 42 | 40 | 40 < 42 | 40 | 50 | right |
| 42 | 45 | 45 > 42 | 40 | 45 | left, empty: stop |
| 63 | 50 | 50 < 63 | 50 | – | right |
| 63 | 70 | 70 > 63 | 50 | 70 | left |
| 63 | 60 | 60 < 63 | 60 | 70 | right |
| 63 | 65 | 65 > 63 | 60 | 65 | left, empty: stop |
So floor(42) = 40, ceiling(42) = 45, floor(63) = 60, ceiling(63) = 65. Floor(10) does not exist (the walk only goes left) and ceiling(90) does not exist (it only goes right). "Closest value in a BST" is floor and ceiling followed by one comparison.
K-th smallest and rank
By the lemma, the k-th smallest key is the k-th key of the inorder sequence. An iterative inorder that stops after pops costs . That is fine once, and too slow if the tree changes and the query repeats.
Size augmentation. Store in every node the number of nodes in its subtree, size = 1 + size(left) + size(right). Insert and delete already walk the path from the root to the change, and only nodes on that path change size, so maintaining it costs extra, nothing asymptotically. Now at node with :
- if , is the answer;
- if , the answer is the k-th smallest in the left subtree;
- otherwise it is the -th smallest in the right subtree.
Trace: kth(7).
| Step | Node | size(left) | k | Decision |
|---|---|---|---|---|
| 1 | 50 | 5 | 7 | 7 > 6: go right, k = 7 − 6 = 1 |
| 2 | 70 | 2 | 1 | 1 ≤ 2: go left |
| 3 | 60 | 0 | 1 | 1 = 0 + 1: answer 60 |
Rank, the number of keys smaller than , is the inverse: walk toward , and every time you go right add size(left) + 1. In the example, rank(45) = 4 (the keys 20, 30, 35, 40). A BST with these two operations is an order-statistic tree (CLRS §17.1 in the 4th edition, §14.1 in the 3rd). Together they answer "how many elements are smaller than me" in a stream, the core of problems like counting inversions online.
Range queries
To list (or count, or sum) the keys in , do an inorder traversal that refuses to enter subtrees that cannot contain answers: enter the left subtree only if , and the right subtree only if .
For on the example tree the traversal visits 50, 30, 40, 35, 45, 70, 60, 65 (8 nodes), skips 20 and 80 entirely, and reports 35 40 45 50 60. In general the visited nodes are the answers plus at most two root-to-leaf boundary paths (one for , one for ), so the cost is for results. With size augmentation, counting the keys in a range is rank(hi + 1) − rank(lo) for integer keys in , with no dependence on .
Building a BST from a sorted array
Given sorted keys, choose the middle element as the root, then build the left half and the right half recursively. The result has height , the minimum possible, and the build takes because each element is touched once. For keys 1 to 10 with mid = (lo + hi) // 2 the result is 5(2(1, 3(., 4)), 8(6(., 7), 9(., 10))), height 3. Contrast inserting the same sorted keys one at a time: height 9.
This is also how you rebalance an unbalanced BST offline: inorder into an array (), rebuild from the middle (). Scapegoat trees (see Variations) do exactly this to subtrees that get too lopsided.
Recovering a BST with two swapped keys
If two keys of a BST are swapped, the inorder sequence is sorted except for those two positions. Swapping 30 and 65 in the example tree changes the inorder sequence from 20 30 35 40 45 50 60 65 70 80 to 20 65 35 40 45 50 60 30 70 80. Scan for inversions, adjacent pairs with :
| Position | Pair | Inversion? | first | second |
|---|---|---|---|---|
| 0 | 20, 65 | no | – | – |
| 1 | 65, 35 | yes | 65 | 35 |
| 2–6 | 35 … 60 | no | 65 | 35 |
| 7 | 60, 30 | yes | 65 | 30 |
| 8 | 30, 70 | no | 65 | 30 |
The first swapped key is the larger element of the first inversion; the second is the smaller element of the last inversion. If the two swapped keys were adjacent in sorted order there is exactly one inversion, and its two elements are the answer, which is why second is set at the first inversion too. Swap the keys of the two nodes back. This runs in time and space with an iterative inorder, or extra space with Morris traversal from Binary Trees & Traversals.
The BST iterator
A BST iterator exposes next() (the next key in sorted order) and hasNext(), using memory instead of materialising all keys. Keep a stack holding the path of "left spine" nodes whose keys have not been returned yet. Initially push the root and all its left descendants. next() pops a node, then pushes its right child and that child's whole left spine, then returns the popped key. Each node is pushed and popped exactly once over a full iteration, so next() is amortized and worst case; the stack never holds more than nodes. The inorder() method in the implementation below is this iterator written as a generator.
The ladder: brute force → better → optimal
Two classic problems show how the invariant and the lemma remove work.
Ladder 1: validating a BST
Rung 1: definition by brute force. For every node, compute the maximum of its left subtree and the minimum of its right subtree and check max(left) < key < min(right). The cost is the sum of subtree sizes (each node is rescanned once per ancestor): balanced, on a chain.
Rung 2: the lemma. Collect the inorder sequence into an array and check that it is strictly increasing. time, extra space. The lemma turns a global property into adjacent pairs.
Rung 3: bounds or a running prev. Pass down an open interval: a left child must lie in , a right child in . Or run inorder remembering only the previous key. time, space, no array, early exit.
The wrong rung everyone tries. Check only left.key < key < right.key at each node. This is and incorrect:
flowchart TD
A["10"] --> B["5"]
A --> C["15"]
C --> D["6"]
C --> E["20"]
D -.->|"6 sits in the right subtree of 10<br/>but is smaller than 10"| A
Every node passes the local check (5 < 10 < 15 and 6 < 15 < 20), yet 6 sits in the right subtree of 10. The inorder sequence 5 10 6 15 20 exposes it immediately. The local check verifies a parent-child relation; the BST property is an ancestor-descendant relation. The bounds method carries the ancestors' constraints down: when we reach 6, its interval is , and 6 fails.
from __future__ import annotations
from dataclasses import dataclass
from typing import Optional
@dataclass
class T:
key: int
left: Optional[T] = None
right: Optional[T] = None
def local_check(n: Optional[T]) -> bool: # WRONG: only parent-child
if n is None:
return True
if n.left and n.left.key >= n.key:
return False
if n.right and n.right.key <= n.key:
return False
return local_check(n.left) and local_check(n.right)
def valid_bounds(n: Optional[T], lo: float = float("-inf"), hi: float = float("inf")) -> bool:
if n is None:
return True
if not lo < n.key < hi:
return False
return valid_bounds(n.left, lo, n.key) and valid_bounds(n.right, n.key, hi)
def valid_inorder(root: Optional[T]) -> bool: # iterative, keeps only prev
stack: list[T] = []
prev, cur = None, root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
if prev is not None and cur.key <= prev:
return False
prev, cur = cur.key, cur.right
return True
bad = T(10, T(5), T(15, T(6), T(20)))
good = T(10, T(5), T(15, T(12), T(20)))
assert local_check(bad) # the trap: says "valid"
assert not valid_bounds(bad) and not valid_inorder(bad)
assert valid_bounds(good) and valid_inorder(good)
assert not valid_bounds(T(1, T(1))) # duplicates rejected (strict)
Ladder 2: k-th smallest
Rung 1. Traverse everything into an array, sort it, index it. . Sorting is redundant: the lemma says inorder is already sorted.
Rung 2. Full inorder into an array, index it. time and space.
Rung 3. Iterative inorder that stops after the k-th pop. time, space. Improvement: only the first keys and one left spine are ever touched.
Rung 4. Size-augmented nodes. per query, independent of , at the cost of one integer per node and upkeep per update. This is the answer to the follow-up "what if the tree is modified often and you query k-th smallest frequently?" (the LeetCode 230 follow-up), and with a balanced tree it is guaranteed.
| Problem | Rung | Time | Extra space | Why it improves |
|---|---|---|---|---|
| Validate | max/min of subtrees per node | worst | — | |
| Validate | inorder into array | lemma: global order becomes adjacent pairs | ||
| Validate | bounds / prev | carries ancestors' constraints, no array, early exit | ||
| k-th | collect + sort | — | ||
| k-th | full inorder | inorder is already sorted | ||
| k-th | inorder, stop at k | touches only the first k keys | ||
| k-th | size-augmented | integers total, per node | skips whole subtrees by count |
Correctness
The individual operations were proved alongside their mechanics (insert, the three delete cases, successor). Here are the remaining arguments, in loop-invariant form so they apply directly to the iterative code.
Search
Invariant: if is in the tree, it is in the subtree rooted at cur.
Initialisation: cur is the root, whose subtree is the whole tree. Maintenance: if , every key in the right subtree and cur itself exceed , so if is present it is in the left subtree; we move there. Symmetric for . Termination: either cur.key = x (found) or cur is empty, whose subtree contains nothing, so by the invariant is absent. Each step moves one level down, so the loop runs at most times.
Floor (ceiling, successor and predecessor are mirrors)
Invariant: best is the largest key among the nodes outside cur's subtree that could possibly matter, and every key that beats best lies in cur's subtree.
When cur.key < x, cur is a valid floor candidate and larger than every previous candidate (we only move right from a candidate, toward larger keys), and the left subtree of cur holds only keys smaller than cur.key, so none of them can beat it; we record it and go right. When cur.key > x, cur and its right subtree are all and cannot be floors; go left. At an empty cur, nothing remains that could beat best. The successor-without-parent proof is the same invariant with "smallest key " and the roles of left and right swapped: the last node where we turned left is the answer.
Bounds-based validation
Claim. A binary tree is a BST if and only if every node's key lies strictly inside the interval obtained by intersecting, over all its ancestors , the half-line if the node is in 's left subtree and if it is in 's right subtree.
This is just the BST property rewritten from the descendant's point of view: "every key in 's left subtree is " is the same set of inequalities as "every node in 's left subtree is below ". The recursion passes down exactly that intersection: going left from replaces by (the new constraint is tighter than the old because was already checked), going right replaces . So valid_bounds checks precisely the conjunction of all ancestor-descendant inequalities. The local check tests only the inequalities between a node and its parent, a strict subset, which is why it accepts the counter-example.
K-th smallest with sizes
Invariant: the answer is the k-th smallest key in cur's subtree (with the current value of ).
Within cur's subtree the inorder sequence is ( keys), then cur, then . Position falls in the first block if , is cur if , and is position of the third block otherwise. Each case preserves the invariant, the depth increases each step, and is maintained, so we never fall off the tree.
Recovering two swapped keys
Let the sorted sequence be and suppose positions were swapped. The new sequence has at position and at position . If the only descent is at position . Otherwise there are exactly two descents: at (because ) and at (because ); every other adjacent pair is untouched and increasing. In both cases the larger element of the first descent is and the smaller element of the last descent is , which are the swapped keys. ∎
Complexity
| Operation | Time | Notes |
|---|---|---|
| search, insert, delete | one root-to-leaf path (delete may walk a second, shorter one to the successor) | |
| min, max, floor, ceiling, successor, predecessor from root | ||
| successor from a node with parent pointers | worst, amortized over a full walk | each edge crossed at most twice |
| kth, rank (size-augmented) | ||
| kth without sizes | ||
| range report of keys | ||
| range count (size-augmented) | via two ranks | |
| build from sorted array | minimum height | |
| build by insertions | expected for random order, for sorted order | |
| full inorder, validate, recover | time, space | space with Morris traversal |
Space is for the nodes. Recursive implementations add stack frames, on a degenerate tree.
Worst case: sorted input
Insert into an empty BST. Each key is larger than every key already present, so it becomes the right child of the current maximum: the tree is a right-leaning chain of height , and building it costs comparisons. Reverse-sorted input gives the mirror image, and nearly-sorted inputs (timestamps, auto-increment IDs) come close. Real data arrives sorted far more often than a random model suggests, the strongest argument for balancing by default.
flowchart LR
subgraph sortedIns["insert 1, 2, 3, 4, 5, 6, 7 in order: height 6"]
A1["1"] --> A2["2"] --> A3["3"] --> A4["4"] --> A5["5"] --> A6["6"] --> A7["7"]
end
subgraph midIns["insert 4, 2, 6, 1, 3, 5, 7: height 2"]
B4["4"] --> B2["2"]
B4 --> B6["6"]
B2 --> B1["1"]
B2 --> B3["3"]
B6 --> B5["5"]
B6 --> B7["7"]
end
How many of the insertion orders produce a chain? The root must be the minimum or the maximum, and recursively for the rest, so orders out of . For that is 512 out of 3,628,800, about 0.014%. Uniformly random orders almost never hit the worst case; real data does it constantly.
Average case: random insertion order
Assume the distinct keys arrive in a uniformly random order. Then the root is equally likely to be any of the keys, and conditioned on the root, the left and right subtrees are themselves random BSTs on the smaller and larger keys. That is precisely the recursion of quicksort with a random pivot: building a random BST performs the same comparisons as quicksort, and the total depth of all nodes equals quicksort's comparison count.
Two quantities matter:
- Average node depth (the cost of a typical successful search, minus one). Its expectation is exactly , where is the -th harmonic number. Since , this is about . A random BST is only about 39% worse than a perfectly balanced tree on average search cost. (Knuth, TAOCP Vol. 3, §6.2.2; Sedgewick & Wayne, Algorithms 4th ed., §3.2.)
- Height (the cost of the worst search in the tree). Devroye (1986) proved that in probability, where is the larger root of . Reed (2003) sharpened this to with , and showed the variance is bounded.
The second-order term matters at practical sizes, as a simulation shows (average over random permutations; height counted in edges, depth with the root at 0):
| n | trials | mean height | mean depth | exact | |||
|---|---|---|---|---|---|---|---|
| 1,000 | 200 | 21.0 | 29.8 | 26.0 | 11.00 | 10.99 | 10.0 |
| 10,000 | 50 | 29.9 | 39.7 | 35.4 | 15.53 | 15.58 | 13.3 |
| 100,000 | 10 | 39.9 | 49.6 | 44.9 | 20.14 | 20.18 | 16.6 |
| 1,000,000 | 3 | 47.7 | 59.6 | 54.4 | 24.51 | 24.79 | 19.9 |
The depth formula is exact and the simulation matches it to two decimals. The height asymptotic overshoots by 6 to 12 levels at these sizes because the term in Reed's formula is negative and sizeable; the ratio of measured height to climbs slowly toward 4.311 (3.04 at , 3.45 at ). Summary: a random million-key BST has typical depth about 25 and worst path about 48, versus 20 balanced. Good, but real inputs are not random permutations.
Deletions break the random model
The analysis assumes insertions only. Hibbard deletion always promotes the successor, which slowly skews the tree: Eppinger (1983) measured average path length growing over long random insert/delete sequences, and Sedgewick & Wayne (§3.2) report height drifting toward roughly . The exact behaviour depends on the update model; the practical fix is to alternate successor and predecessor, or better, use a balanced tree.
Constants and cache behaviour
Each level is a pointer dereference to a heap node; once the tree outgrows the caches, each can be a miss costing on the order of 100 ns, so 20 levels for a million keys can cost microseconds, where a hash table pays one or two misses. Node overhead is also significant: a libstdc++ std::map node carries a colour field and three pointers (32 bytes on a 64-bit build) before the key and value, and a Java TreeMap.Entry holds key, value, left, right, parent and colour fields plus an object header. This is exactly why on-disk and in-memory database indexes use B-trees with hundreds of keys per node (see Balanced BSTs and Indexing Deep Dive): fewer, fatter levels.
Implementation
The canonical implementation: an unbalanced BST over distinct integer keys with subtree sizes. It supports search, insert, three-case delete, floor, ceiling, successor, predecessor, k-th smallest, rank, range report, an iterative inorder iterator, height, and a validator that checks both the BST property (bounds method) and the size fields. Insert and delete are recursive so sizes can be recomputed on the way back up; everything else is iterative. The tests are the traces from this page plus a degenerate sorted-insert case.
from __future__ import annotations
from dataclasses import dataclass
from typing import Iterator, Optional
@dataclass
class Node:
key: int
left: Optional[Node] = None
right: Optional[Node] = None
size: int = 1 # number of nodes in this subtree
def _size(n: Optional[Node]) -> int:
return n.size if n else 0
class BST:
"""Unbalanced binary search tree with distinct keys and subtree sizes."""
def __init__(self) -> None:
self.root: Optional[Node] = None
def __len__(self) -> int:
return _size(self.root)
# ---- search -------------------------------------------------------
def contains(self, key: int) -> bool:
cur = self.root
while cur:
if key == cur.key:
return True
cur = cur.left if key < cur.key else cur.right
return False
# ---- insert (recursive so sizes can be fixed on the way back up) ---
def insert(self, key: int) -> None:
if not self.contains(key): # keep sizes exact: no-op on duplicates
self.root = self._insert(self.root, key)
def _insert(self, n: Optional[Node], key: int) -> Node:
if n is None:
return Node(key)
if key < n.key:
n.left = self._insert(n.left, key)
else:
n.right = self._insert(n.right, key)
n.size += 1
return n
# ---- delete: leaf / one child / two children ------------------------
def delete(self, key: int) -> None:
if self.contains(key):
self.root = self._delete(self.root, key)
def _delete(self, n: Optional[Node], key: int) -> Optional[Node]:
assert n is not None
if key < n.key:
n.left = self._delete(n.left, key)
elif key > n.key:
n.right = self._delete(n.right, key)
else:
if n.left is None: # cases 1 and 2
return n.right
if n.right is None:
return n.left
succ = n.right # case 3: inorder successor
while succ.left:
succ = succ.left
n.key = succ.key
n.right = self._delete(n.right, succ.key)
n.size = 1 + _size(n.left) + _size(n.right)
return n
# ---- order queries -------------------------------------------------
def floor(self, x: int) -> Optional[int]:
cur, best = self.root, None
while cur:
if cur.key == x:
return x
if cur.key < x:
best, cur = cur.key, cur.right
else:
cur = cur.left
return best
def ceiling(self, x: int) -> Optional[int]:
cur, best = self.root, None
while cur:
if cur.key == x:
return x
if cur.key > x:
best, cur = cur.key, cur.left
else:
cur = cur.right
return best
def successor(self, x: int) -> Optional[int]: # smallest key > x
cur, best = self.root, None
while cur:
if x < cur.key:
best, cur = cur.key, cur.left
else:
cur = cur.right
return best
def predecessor(self, x: int) -> Optional[int]: # largest key < x
cur, best = self.root, None
while cur:
if x > cur.key:
best, cur = cur.key, cur.right
else:
cur = cur.left
return best
def kth(self, k: int) -> int: # 1-indexed k-th smallest
if not 1 <= k <= len(self):
raise IndexError(k)
cur = self.root
while cur:
ls = _size(cur.left)
if k == ls + 1:
return cur.key
if k <= ls:
cur = cur.left
else:
k -= ls + 1
cur = cur.right
raise AssertionError("unreachable")
def rank(self, x: int) -> int: # number of keys < x
cur, r = self.root, 0
while cur:
if x <= cur.key:
cur = cur.left
else:
r += _size(cur.left) + 1
cur = cur.right
return r
def range(self, lo: int, hi: int) -> list[int]: # keys in [lo, hi], sorted
out: list[int] = []
def go(n: Optional[Node]) -> None:
if n is None:
return
if lo < n.key:
go(n.left)
if lo <= n.key <= hi:
out.append(n.key)
if n.key < hi:
go(n.right)
go(self.root)
return out
def inorder(self) -> Iterator[int]: # iterative, O(h) stack
stack: list[Node] = []
cur = self.root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
yield cur.key
cur = cur.right
def height(self) -> int: # edges; empty tree = -1
def h(n: Optional[Node]) -> int:
return -1 if n is None else 1 + max(h(n.left), h(n.right))
return h(self.root)
def is_valid(self) -> bool: # min/max bounds + sizes
def ok(n: Optional[Node], lo: Optional[int], hi: Optional[int]) -> bool:
if n is None:
return True
if (lo is not None and n.key <= lo) or (hi is not None and n.key >= hi):
return False
if n.size != 1 + _size(n.left) + _size(n.right):
return False
return ok(n.left, lo, n.key) and ok(n.right, n.key, hi)
return ok(self.root, None, None)
if __name__ == "__main__":
t = BST()
for k in [50, 30, 70, 20, 40, 60, 80, 35, 45, 65]:
t.insert(k)
t.insert(40) # duplicate: ignored
assert len(t) == 10 and t.is_valid()
assert list(t.inorder()) == [20, 30, 35, 40, 45, 50, 60, 65, 70, 80]
assert t.contains(45) and not t.contains(42)
assert t.height() == 3
assert (t.floor(42), t.ceiling(42)) == (40, 45)
assert (t.floor(63), t.ceiling(63)) == (60, 65)
assert t.floor(10) is None and t.ceiling(90) is None
assert t.successor(45) == 50 and t.successor(80) is None
assert t.predecessor(60) == 50 and t.predecessor(20) is None
assert t.kth(1) == 20 and t.kth(7) == 60 and t.kth(10) == 80
assert t.rank(45) == 4 and t.rank(100) == 10
assert t.range(33, 62) == [35, 40, 45, 50, 60]
t.delete(20) # leaf
t.delete(60) # one child
t.delete(50) # two children -> successor 65
t.delete(99) # absent: no-op
assert t.is_valid() and len(t) == 7
assert t.root is not None and t.root.key == 65
assert list(t.inorder()) == [30, 35, 40, 45, 65, 70, 80]
assert t.kth(4) == 45
s = BST() # sorted input degenerates
for k in range(200):
s.insert(k)
assert s.height() == 199 and s.is_valid()
print("BST OK")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class BST {
static final class Node {
int key, size = 1;
Node left, right;
Node(int key) { this.key = key; }
}
private Node root;
private static int size(Node n) { return n == null ? 0 : n.size; }
public int size() { return size(root); }
public boolean contains(int key) {
Node cur = root;
while (cur != null) {
if (key == cur.key) return true;
cur = key < cur.key ? cur.left : cur.right;
}
return false;
}
public void insert(int key) {
if (!contains(key)) root = insert(root, key); // no-op on duplicates
}
private Node insert(Node n, int key) {
if (n == null) return new Node(key);
if (key < n.key) n.left = insert(n.left, key);
else n.right = insert(n.right, key);
n.size++;
return n;
}
public void delete(int key) {
if (contains(key)) root = delete(root, key);
}
private Node delete(Node n, int key) {
if (key < n.key) n.left = delete(n.left, key);
else if (key > n.key) n.right = delete(n.right, key);
else {
if (n.left == null) return n.right; // cases 1 and 2
if (n.right == null) return n.left;
Node succ = n.right; // case 3
while (succ.left != null) succ = succ.left;
n.key = succ.key;
n.right = delete(n.right, succ.key);
}
n.size = 1 + size(n.left) + size(n.right);
return n;
}
public Integer floor(int x) {
Node cur = root; Integer best = null;
while (cur != null) {
if (cur.key == x) return x;
if (cur.key < x) { best = cur.key; cur = cur.right; }
else cur = cur.left;
}
return best;
}
public Integer ceiling(int x) {
Node cur = root; Integer best = null;
while (cur != null) {
if (cur.key == x) return x;
if (cur.key > x) { best = cur.key; cur = cur.left; }
else cur = cur.right;
}
return best;
}
public Integer successor(int x) {
Node cur = root; Integer best = null;
while (cur != null) {
if (x < cur.key) { best = cur.key; cur = cur.left; }
else cur = cur.right;
}
return best;
}
public Integer predecessor(int x) {
Node cur = root; Integer best = null;
while (cur != null) {
if (x > cur.key) { best = cur.key; cur = cur.right; }
else cur = cur.left;
}
return best;
}
public int kth(int k) { // 1-indexed
if (k < 1 || k > size()) throw new IndexOutOfBoundsException(k);
Node cur = root;
while (true) {
int ls = size(cur.left);
if (k == ls + 1) return cur.key;
if (k <= ls) cur = cur.left;
else { k -= ls + 1; cur = cur.right; }
}
}
public int rank(int x) { // keys < x
Node cur = root; int r = 0;
while (cur != null) {
if (x <= cur.key) cur = cur.left;
else { r += size(cur.left) + 1; cur = cur.right; }
}
return r;
}
public List<Integer> range(int lo, int hi) {
List<Integer> out = new ArrayList<>();
range(root, lo, hi, out);
return out;
}
private void range(Node n, int lo, int hi, List<Integer> out) {
if (n == null) return;
if (lo < n.key) range(n.left, lo, hi, out);
if (lo <= n.key && n.key <= hi) out.add(n.key);
if (n.key < hi) range(n.right, lo, hi, out);
}
public List<Integer> inorder() { // iterative
List<Integer> out = new ArrayList<>();
Deque<Node> stack = new ArrayDeque<>();
Node cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) { stack.push(cur); cur = cur.left; }
cur = stack.pop();
out.add(cur.key);
cur = cur.right;
}
return out;
}
public int height() { return height(root); }
private static int height(Node n) {
return n == null ? -1 : 1 + Math.max(height(n.left), height(n.right));
}
public boolean isValid() { return valid(root, Long.MIN_VALUE, Long.MAX_VALUE); }
private static boolean valid(Node n, long lo, long hi) { // open interval (lo, hi)
if (n == null) return true;
if (n.key <= lo || n.key >= hi) return false;
if (n.size != 1 + size(n.left) + size(n.right)) return false;
return valid(n.left, lo, n.key) && valid(n.right, n.key, hi);
}
static void check(boolean cond, String msg) {
if (!cond) throw new AssertionError(msg);
}
public static void main(String[] args) {
BST t = new BST();
for (int k : new int[]{50, 30, 70, 20, 40, 60, 80, 35, 45, 65}) t.insert(k);
t.insert(40);
check(t.size() == 10 && t.isValid(), "size/valid");
check(t.inorder().equals(List.of(20, 30, 35, 40, 45, 50, 60, 65, 70, 80)), "inorder");
check(t.contains(45) && !t.contains(42), "contains");
check(t.height() == 3, "height");
check(t.floor(42) == 40 && t.ceiling(42) == 45, "floor/ceil 42");
check(t.floor(63) == 60 && t.ceiling(63) == 65, "floor/ceil 63");
check(t.floor(10) == null && t.ceiling(90) == null, "floor/ceil none");
check(t.successor(45) == 50 && t.successor(80) == null, "successor");
check(t.predecessor(60) == 50 && t.predecessor(20) == null, "predecessor");
check(t.kth(1) == 20 && t.kth(7) == 60 && t.kth(10) == 80, "kth");
check(t.rank(45) == 4 && t.rank(100) == 10, "rank");
check(t.range(33, 62).equals(List.of(35, 40, 45, 50, 60)), "range");
t.delete(20); t.delete(60); t.delete(50); t.delete(99);
check(t.isValid() && t.size() == 7, "after delete");
check(t.root.key == 65, "root is successor");
check(t.inorder().equals(List.of(30, 35, 40, 45, 65, 70, 80)), "inorder after delete");
check(t.kth(4) == 45, "kth after delete");
BST s = new BST();
for (int k = 0; k < 200; k++) s.insert(k);
check(s.height() == 199 && s.isValid(), "degenerate");
System.out.println("BST OK");
}
}
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <limits>
#include <memory>
#include <optional>
#include <stdexcept>
#include <vector>
class BST {
struct Node {
int key;
int size = 1;
std::unique_ptr<Node> left, right;
explicit Node(int k) : key(k) {}
};
using Ptr = std::unique_ptr<Node>;
Ptr root_;
static int sz(const Ptr& n) { return n ? n->size : 0; }
static void insert(Ptr& n, int key) {
if (!n) { n = std::make_unique<Node>(key); return; }
insert(key < n->key ? n->left : n->right, key);
++n->size;
}
static void erase(Ptr& n, int key) {
if (key < n->key) erase(n->left, key);
else if (key > n->key) erase(n->right, key);
else {
if (!n->left) { n = std::move(n->right); return; } // cases 1 and 2
if (!n->right) { n = std::move(n->left); return; }
Node* succ = n->right.get(); // case 3
while (succ->left) succ = succ->left.get();
n->key = succ->key;
erase(n->right, succ->key);
}
n->size = 1 + sz(n->left) + sz(n->right);
}
static void range(const Ptr& n, int lo, int hi, std::vector<int>& out) {
if (!n) return;
if (lo < n->key) range(n->left, lo, hi, out);
if (lo <= n->key && n->key <= hi) out.push_back(n->key);
if (n->key < hi) range(n->right, lo, hi, out);
}
static int height(const Ptr& n) {
return n ? 1 + std::max(height(n->left), height(n->right)) : -1;
}
static bool valid(const Ptr& n, long long lo, long long hi) {
if (!n) return true;
if (n->key <= lo || n->key >= hi) return false;
if (n->size != 1 + sz(n->left) + sz(n->right)) return false;
return valid(n->left, lo, n->key) && valid(n->right, n->key, hi);
}
public:
int size() const { return sz(root_); }
int rootKey() const { return root_->key; }
bool contains(int key) const {
const Node* cur = root_.get();
while (cur) {
if (key == cur->key) return true;
cur = key < cur->key ? cur->left.get() : cur->right.get();
}
return false;
}
void insert(int key) { if (!contains(key)) insert(root_, key); }
void erase(int key) { if (contains(key)) erase(root_, key); }
std::optional<int> floor(int x) const {
const Node* cur = root_.get(); std::optional<int> best;
while (cur) {
if (cur->key == x) return x;
if (cur->key < x) { best = cur->key; cur = cur->right.get(); }
else cur = cur->left.get();
}
return best;
}
std::optional<int> ceiling(int x) const {
const Node* cur = root_.get(); std::optional<int> best;
while (cur) {
if (cur->key == x) return x;
if (cur->key > x) { best = cur->key; cur = cur->left.get(); }
else cur = cur->right.get();
}
return best;
}
std::optional<int> successor(int x) const {
const Node* cur = root_.get(); std::optional<int> best;
while (cur) {
if (x < cur->key) { best = cur->key; cur = cur->left.get(); }
else cur = cur->right.get();
}
return best;
}
std::optional<int> predecessor(int x) const {
const Node* cur = root_.get(); std::optional<int> best;
while (cur) {
if (x > cur->key) { best = cur->key; cur = cur->right.get(); }
else cur = cur->left.get();
}
return best;
}
int kth(int k) const { // 1-indexed
if (k < 1 || k > size()) throw std::out_of_range("kth");
const Node* cur = root_.get();
while (true) {
int ls = sz(cur->left);
if (k == ls + 1) return cur->key;
if (k <= ls) cur = cur->left.get();
else { k -= ls + 1; cur = cur->right.get(); }
}
}
int rank(int x) const { // keys < x
const Node* cur = root_.get(); int r = 0;
while (cur) {
if (x <= cur->key) cur = cur->left.get();
else { r += sz(cur->left) + 1; cur = cur->right.get(); }
}
return r;
}
std::vector<int> range(int lo, int hi) const {
std::vector<int> out;
range(root_, lo, hi, out);
return out;
}
std::vector<int> inorder() const { // iterative
std::vector<int> out;
std::vector<const Node*> stack;
const Node* cur = root_.get();
while (cur || !stack.empty()) {
while (cur) { stack.push_back(cur); cur = cur->left.get(); }
cur = stack.back(); stack.pop_back();
out.push_back(cur->key);
cur = cur->right.get();
}
return out;
}
int height() const { return height(root_); }
bool isValid() const {
return valid(root_, std::numeric_limits<long long>::min(), std::numeric_limits<long long>::max());
}
};
static void check(bool cond, const char* msg) {
if (!cond) { std::fprintf(stderr, "FAILED: %s\n", msg); std::exit(1); }
}
int main() {
BST t;
for (int k : {50, 30, 70, 20, 40, 60, 80, 35, 45, 65}) t.insert(k);
t.insert(40);
check(t.size() == 10 && t.isValid(), "size/valid");
check(t.inorder() == std::vector<int>{20, 30, 35, 40, 45, 50, 60, 65, 70, 80}, "inorder");
check(t.contains(45) && !t.contains(42), "contains");
check(t.height() == 3, "height");
check(t.floor(42) == 40 && t.ceiling(42) == 45, "floor/ceil 42");
check(t.floor(63) == 60 && t.ceiling(63) == 65, "floor/ceil 63");
check(!t.floor(10) && !t.ceiling(90), "floor/ceil none");
check(t.successor(45) == 50 && !t.successor(80), "successor");
check(t.predecessor(60) == 50 && !t.predecessor(20), "predecessor");
check(t.kth(1) == 20 && t.kth(7) == 60 && t.kth(10) == 80, "kth");
check(t.rank(45) == 4 && t.rank(100) == 10, "rank");
check(t.range(33, 62) == std::vector<int>{35, 40, 45, 50, 60}, "range");
t.erase(20); t.erase(60); t.erase(50); t.erase(99);
check(t.isValid() && t.size() == 7, "after erase");
check(t.rootKey() == 65, "root is successor");
check(t.inorder() == std::vector<int>{30, 35, 40, 45, 65, 70, 80}, "inorder after erase");
check(t.kth(4) == 45, "kth after erase");
BST s;
for (int k = 0; k < 200; ++k) s.insert(k);
check(s.height() == 199 && s.isValid(), "degenerate");
std::puts("BST OK");
}
class BSTNode {
key: number;
size = 1;
left: BSTNode | null = null;
right: BSTNode | null = null;
constructor(key: number) {
this.key = key;
}
}
const sz = (n: BSTNode | null): number => (n ? n.size : 0);
class BST {
root: BSTNode | null = null;
get size(): number {
return sz(this.root);
}
contains(key: number): boolean {
let cur = this.root;
while (cur) {
if (key === cur.key) return true;
cur = key < cur.key ? cur.left : cur.right;
}
return false;
}
insert(key: number): void {
if (!this.contains(key)) this.root = this.insertAt(this.root, key);
}
private insertAt(n: BSTNode | null, key: number): BSTNode {
if (!n) return new BSTNode(key);
if (key < n.key) n.left = this.insertAt(n.left, key);
else n.right = this.insertAt(n.right, key);
n.size++;
return n;
}
delete(key: number): void {
if (this.contains(key)) this.root = this.deleteAt(this.root!, key);
}
private deleteAt(n: BSTNode, key: number): BSTNode | null {
if (key < n.key) n.left = this.deleteAt(n.left!, key);
else if (key > n.key) n.right = this.deleteAt(n.right!, key);
else {
if (!n.left) return n.right; // cases 1 and 2
if (!n.right) return n.left;
let succ = n.right; // case 3
while (succ.left) succ = succ.left;
n.key = succ.key;
n.right = this.deleteAt(n.right, succ.key);
}
n.size = 1 + sz(n.left) + sz(n.right);
return n;
}
floor(x: number): number | null {
let cur = this.root;
let best: number | null = null;
while (cur) {
if (cur.key === x) return x;
if (cur.key < x) { best = cur.key; cur = cur.right; }
else cur = cur.left;
}
return best;
}
ceiling(x: number): number | null {
let cur = this.root;
let best: number | null = null;
while (cur) {
if (cur.key === x) return x;
if (cur.key > x) { best = cur.key; cur = cur.left; }
else cur = cur.right;
}
return best;
}
successor(x: number): number | null {
let cur = this.root;
let best: number | null = null;
while (cur) {
if (x < cur.key) { best = cur.key; cur = cur.left; }
else cur = cur.right;
}
return best;
}
predecessor(x: number): number | null {
let cur = this.root;
let best: number | null = null;
while (cur) {
if (x > cur.key) { best = cur.key; cur = cur.right; }
else cur = cur.left;
}
return best;
}
kth(k: number): number {
if (k < 1 || k > this.size) throw new RangeError(`kth(${k})`);
let cur = this.root!;
while (true) {
const ls = sz(cur.left);
if (k === ls + 1) return cur.key;
if (k <= ls) cur = cur.left!;
else { k -= ls + 1; cur = cur.right!; }
}
}
rank(x: number): number {
let cur = this.root;
let r = 0;
while (cur) {
if (x <= cur.key) cur = cur.left;
else { r += sz(cur.left) + 1; cur = cur.right; }
}
return r;
}
range(lo: number, hi: number): number[] {
const out: number[] = [];
const go = (n: BSTNode | null): void => {
if (!n) return;
if (lo < n.key) go(n.left);
if (lo <= n.key && n.key <= hi) out.push(n.key);
if (n.key < hi) go(n.right);
};
go(this.root);
return out;
}
*inorder(): Generator<number> {
const stack: BSTNode[] = [];
let cur = this.root;
while (cur || stack.length) {
while (cur) { stack.push(cur); cur = cur.left; }
cur = stack.pop()!;
yield cur.key;
cur = cur.right;
}
}
height(): number {
const h = (n: BSTNode | null): number => (n ? 1 + Math.max(h(n.left), h(n.right)) : -1);
return h(this.root);
}
isValid(): boolean {
const ok = (n: BSTNode | null, lo: number, hi: number): boolean => {
if (!n) return true;
if (n.key <= lo || n.key >= hi) return false;
if (n.size !== 1 + sz(n.left) + sz(n.right)) return false;
return ok(n.left, lo, n.key) && ok(n.right, n.key, hi);
};
return ok(this.root, -Infinity, Infinity);
}
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error("FAILED: " + msg);
}
const same = (a: number[], b: number[]): boolean =>
a.length === b.length && a.every((v, i) => v === b[i]);
const t = new BST();
for (const k of [50, 30, 70, 20, 40, 60, 80, 35, 45, 65]) t.insert(k);
t.insert(40);
check(t.size === 10 && t.isValid(), "size/valid");
check(same([...t.inorder()], [20, 30, 35, 40, 45, 50, 60, 65, 70, 80]), "inorder");
check(t.contains(45) && !t.contains(42), "contains");
check(t.height() === 3, "height");
check(t.floor(42) === 40 && t.ceiling(42) === 45, "floor/ceil 42");
check(t.floor(63) === 60 && t.ceiling(63) === 65, "floor/ceil 63");
check(t.floor(10) === null && t.ceiling(90) === null, "floor/ceil none");
check(t.successor(45) === 50 && t.successor(80) === null, "successor");
check(t.predecessor(60) === 50 && t.predecessor(20) === null, "predecessor");
check(t.kth(1) === 20 && t.kth(7) === 60 && t.kth(10) === 80, "kth");
check(t.rank(45) === 4 && t.rank(100) === 10, "rank");
check(same(t.range(33, 62), [35, 40, 45, 50, 60]), "range");
t.delete(20); t.delete(60); t.delete(50); t.delete(99);
check(t.isValid() && t.size === 7, "after delete");
check(t.root !== null && t.root.key === 65, "root is successor");
check(same([...t.inorder()], [30, 35, 40, 45, 65, 70, 80]), "inorder after delete");
check(t.kth(4) === 45, "kth after delete");
const s = new BST();
for (let k = 0; k < 200; k++) s.insert(k);
check(s.height() === 199 && s.isValid(), "degenerate");
console.log("BST OK");
A few implementation choices worth calling out:
- Duplicates are rejected by checking
containsfirst; otherwise sizes along the path would be incremented wrongly. Production code avoids the double walk by having insert report whether it created a node. - Delete copies the successor's key into the doomed node rather than relinking nodes. That is simpler, but it invalidates any outside pointer to the successor node, which is why
std::mapandTreeMapinstead relink the successor node into the deleted node's position: iterators to other elements must stay valid after an erase. - Validation checks sizes too: an augmented tree has two invariants, and a bug in either breaks queries silently.
Variant: ordered maps in each language
In real code you use your language's ordered map, which is a balanced BST (or, in Python's case, something cleverer). The operations on this page map onto library calls as follows.
| Operation | Java TreeMap / TreeSet | C++ std::map / std::set | Python | TypeScript / JavaScript |
|---|---|---|---|---|
| structure | red-black tree | red-black tree in libstdc++, libc++ and MSVC (the standard only fixes the complexity) | no built-in; sortedcontainers.SortedList / SortedDict (third-party) | no built-in; Map is insertion-ordered, not sorted |
| floor / ceiling | floorKey, ceilingKey | prev(upper_bound(x)), lower_bound(x) | SortedList.bisect_right, bisect_left | write it (sorted array + binary search, or a tree library) |
| strict successor / predecessor | higherKey, lowerKey | upper_bound(x), prev(lower_bound(x)) | bisect_right, bisect_left − 1 | — |
| range view | subMap, headMap, tailMap (live views) | iterate [lower_bound(lo), upper_bound(hi)) | irange(lo, hi) | — |
| k-th smallest | not supported (iterate) | not supported in std; GNU __gnu_pbds::tree with tree_order_statistics_node_update has find_by_order / order_of_key | SortedList[k] | — |
| min / max / pop | firstKey, lastKey, pollFirstEntry | begin(), rbegin(), erase(begin()) | sl[0], sl[-1], sl.pop(0) | — |
sortedcontainers is not a tree: it keeps a list of sorted sublists (default load factor 1,000) plus a positional index, so inserts shift at most about a thousand elements, and in CPython, where every node is a heavyweight object, it beats pure-Python balanced trees. Positional indexing makes k-th smallest sl[k].
# fragment — requires the third-party package: pip install sortedcontainers
from sortedcontainers import SortedList
sl = SortedList([50, 30, 70, 20, 40, 60, 80])
sl.add(45)
sl[sl.bisect_right(42) - 1] # floor(42) -> 40
sl[sl.bisect_left(42)] # ceiling(42) -> 45
sl[3] # 4th smallest -> 45
list(sl.irange(33, 62)) # [40, 45, 50, 60]
The standard-library equivalents, with the same test data in all four languages (Python and TypeScript fall back to a sorted array, which is the right tool when reads dominate writes):
import bisect
# Python has no ordered map in the standard library. For read-mostly data a
# sorted list + bisect gives O(log n) queries (O(n) inserts); for heavy updates
# use the third-party sortedcontainers.SortedList / SortedDict.
keys = sorted([50, 30, 70, 20, 40, 60, 80])
def floor_key(a: list[int], x: int) -> int | None: # largest <= x
i = bisect.bisect_right(a, x)
return a[i - 1] if i else None
def ceiling_key(a: list[int], x: int) -> int | None: # smallest >= x
i = bisect.bisect_left(a, x)
return a[i] if i < len(a) else None
def higher_key(a: list[int], x: int) -> int | None: # smallest > x
i = bisect.bisect_right(a, x)
return a[i] if i < len(a) else None
def count_in_range(a: list[int], lo: int, hi: int) -> int: # keys in [lo, hi]
return bisect.bisect_right(a, hi) - bisect.bisect_left(a, lo)
bisect.insort(keys, 45) # O(n) shift, fine for small n
assert keys == [20, 30, 40, 45, 50, 60, 70, 80]
assert floor_key(keys, 42) == 40 and ceiling_key(keys, 42) == 45
assert floor_key(keys, 10) is None and ceiling_key(keys, 90) is None
assert higher_key(keys, 45) == 50
assert count_in_range(keys, 33, 62) == 4 # 40, 45, 50, 60
assert keys[3] == 45 # k-th smallest is just indexing
print("ordered map OK")
import java.util.List;
import java.util.NavigableMap;
import java.util.TreeMap;
public class OrderedMapDemo {
static void check(boolean cond, String msg) {
if (!cond) throw new AssertionError(msg);
}
public static void main(String[] args) {
TreeMap<Integer, String> m = new TreeMap<>(); // red-black tree
for (int k : new int[]{50, 30, 70, 20, 40, 60, 80}) m.put(k, "v" + k);
m.put(45, "v45");
check(List.copyOf(m.keySet()).equals(List.of(20, 30, 40, 45, 50, 60, 70, 80)), "sorted keys");
check(m.floorKey(42) == 40 && m.ceilingKey(42) == 45, "floor/ceiling");
check(m.floorKey(10) == null && m.ceilingKey(90) == null, "missing");
check(m.higherKey(45) == 50 && m.lowerKey(45) == 40, "higher/lower");
NavigableMap<Integer, String> sub = m.subMap(33, true, 62, true);
check(sub.size() == 4 && sub.firstKey() == 40 && sub.lastKey() == 60, "subMap view");
check(m.firstKey() == 20 && m.lastKey() == 80, "min/max");
check(m.pollFirstEntry().getKey() == 20 && m.size() == 7, "pollFirst");
System.out.println("ordered map OK");
}
}
#include <cstdio>
#include <cstdlib>
#include <iterator>
#include <map>
#include <optional>
#include <string>
static void check(bool cond, const char* msg) {
if (!cond) { std::fprintf(stderr, "FAILED: %s\n", msg); std::exit(1); }
}
// std::map has lower_bound (first key >= x) and upper_bound (first key > x).
// floor and ceiling are built from them.
template <class M>
std::optional<int> floorKey(const M& m, int x) {
auto it = m.upper_bound(x);
if (it == m.begin()) return std::nullopt;
return std::prev(it)->first;
}
template <class M>
std::optional<int> ceilingKey(const M& m, int x) {
auto it = m.lower_bound(x);
if (it == m.end()) return std::nullopt;
return it->first;
}
int main() {
std::map<int, std::string> m; // red-black tree in libstdc++, libc++ and MSVC
for (int k : {50, 30, 70, 20, 40, 60, 80}) m[k] = "v" + std::to_string(k);
m.emplace(45, "v45");
check(floorKey(m, 42) == 40 && ceilingKey(m, 42) == 45, "floor/ceiling");
check(!floorKey(m, 10) && !ceilingKey(m, 90), "missing");
check(m.upper_bound(45)->first == 50, "higher");
auto lo = m.lower_bound(33), hi = m.upper_bound(62);
check(std::distance(lo, hi) == 4, "range count is O(log n + k)");
check(m.begin()->first == 20 && m.rbegin()->first == 80, "min/max");
m.erase(m.begin());
check(m.size() == 7 && m.begin()->first == 30, "erase min");
std::puts("ordered map OK");
}
// JavaScript has no built-in ordered map (Map iterates in insertion order).
// For read-mostly data, a sorted array + binary search does the job; for
// heavy updates, bring a balanced tree or skip list library, or write the BST above.
function lowerBound(a: number[], x: number): number { // first index with a[i] >= x
let lo = 0, hi = a.length;
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (a[mid] < x) lo = mid + 1; else hi = mid;
}
return lo;
}
function upperBound(a: number[], x: number): number { // first index with a[i] > x
let lo = 0, hi = a.length;
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (a[mid] <= x) lo = mid + 1; else hi = mid;
}
return lo;
}
const floorKey = (a: number[], x: number): number | null => {
const i = upperBound(a, x);
return i ? a[i - 1] : null;
};
const ceilingKey = (a: number[], x: number): number | null => {
const i = lowerBound(a, x);
return i < a.length ? a[i] : null;
};
function insertSorted(a: number[], x: number): void {
const i = lowerBound(a, x);
if (a[i] !== x) a.splice(i, 0, x); // O(n) shift
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error("FAILED: " + msg);
}
const keys = [50, 30, 70, 20, 40, 60, 80].sort((x, y) => x - y); // numeric comparator!
insertSorted(keys, 45);
check(keys.join() === "20,30,40,45,50,60,70,80", "sorted keys");
check(floorKey(keys, 42) === 40 && ceilingKey(keys, 42) === 45, "floor/ceiling");
check(floorKey(keys, 10) === null && ceilingKey(keys, 90) === null, "missing");
check(keys[upperBound(keys, 45)] === 50, "higher");
check(upperBound(keys, 62) - lowerBound(keys, 33) === 4, "range count");
check(keys[3] === 45, "k-th smallest is indexing");
console.log("ordered map OK");
Two traps: TreeMap.floorKey returns a boxed Integer, so m.floorKey(x) == y throws NullPointerException when there is no floor; and JavaScript's default sort compares as strings ([10, 9].sort() gives [10, 9]).
Variant: sorted array to BST, and the iterator as a class
from __future__ import annotations
from dataclasses import dataclass
from typing import Optional
@dataclass
class TreeNode:
val: int
left: Optional[TreeNode] = None
right: Optional[TreeNode] = None
def sorted_array_to_bst(a: list[int]) -> Optional[TreeNode]:
def build(lo: int, hi: int) -> Optional[TreeNode]:
if lo > hi:
return None
mid = (lo + hi) // 2
return TreeNode(a[mid], build(lo, mid - 1), build(mid + 1, hi))
return build(0, len(a) - 1)
class BSTIterator:
"""next() is O(1) amortized, O(h) worst; memory O(h)."""
def __init__(self, root: Optional[TreeNode]) -> None:
self.stack: list[TreeNode] = []
self._push_left(root)
def _push_left(self, n: Optional[TreeNode]) -> None:
while n:
self.stack.append(n)
n = n.left
def has_next(self) -> bool:
return bool(self.stack)
def next(self) -> int:
n = self.stack.pop()
self._push_left(n.right)
return n.val
def height(n: Optional[TreeNode]) -> int:
return -1 if n is None else 1 + max(height(n.left), height(n.right))
root = sorted_array_to_bst(list(range(1, 11)))
assert root is not None and root.val == 5 and height(root) == 3
it, out = BSTIterator(root), []
while it.has_next():
out.append(it.next())
assert out == list(range(1, 11))
assert height(sorted_array_to_bst(list(range(1000)))) == 9 # ceil(log2(1001)) - 1
Real-world uses
- Ordered maps in standard libraries. Java's
TreeMapandTreeSetare red-black trees (the Javadoc says so and credits CLRS);ConcurrentSkipListMapis the concurrent ordered alternative. C++'sstd::map,std::set,std::multimapandstd::multisetare red-black trees in all three major standard libraries. See Your Language's Data Structures. - Operating system kernels. The Linux kernel's generic red-black tree (
lib/rbtree.c) sits under the CPU scheduler's run queue (keyed by virtual runtime under CFS; see CPU Scheduling), high-resolution timers, and per-process memory-area lookups in older kernels (newer kernels moved VMAs to a maple tree). - Timers. nginx keeps timers in a red-black tree (
ngx_rbtree): next timeout = minimum, add/cancel = insert/delete. Event loops that never cancel arbitrary timers use heaps instead. - Databases. B-tree indexes obey the same invariant with many keys per node. Index range scans are this page's range query;
ORDER BY ... LIMIT kon an indexed column is "walk the inorder sequence and stop after k". See Indexing Deep Dive and Storage Engines. In-memory write buffers (memtables) in LSM-tree stores are typically skip lists, the probabilistic cousin covered in Treaps, Splay Trees & Skip Lists. - Interval and address lookups. Non-overlapping ranges keyed by their start answer "which range contains address ?" with one floor query. Overlapping intervals need an augmented BST (interval tree) or the sweeps in Intervals.
- Order statistics. Size-augmented trees (GNU
pb_ds, hand-written treaps) answer rank and k-th under updates: online inversion counts, sliding-window medians, leaderboards. Redis sorted sets answer the same rank queries with a skip list whose links carry span counts, the skip-list analogue of subtree sizes (see Redis Internals).
Pitfalls & edge cases
- The local validation check. Comparing a node only with its children accepts invalid trees. Use bounds or inorder. This is the number one BST interview bug.
- Integer bounds in validation. Initialising bounds with
Integer.MIN_VALUE/INT_MINand using strict comparisons rejects a valid tree that contains that exact value. Uselongbounds, nullable bounds, or in languages that have it. - Duplicates. Decide the policy up front. If equal keys go right, validation becomes
lo <= key < hi; inserting duplicates into a size-augmented tree that assumes distinct keys corrupts every count. - Deleting the root. If your delete returns the new subtree root, assign it back (
root = delete(root, key)). Forgetting this works for every node except the root, and for the root only when it has two children (where the key is copied in place), which makes the bug intermittent. - Copy-key deletion and external references. Copying the successor's key into the deleted node silently changes what an outside pointer to "the node holding 65" refers to. Libraries relink nodes instead. If you hand out node handles, do the same.
- Recursion depth. On a degenerate tree recursion goes deep (CPython stops at 1,000 frames by default). Iterate for search, floor, kth and traversal; balance the tree for untrusted input.
- Sorted or nearly sorted input. Auto-increment IDs and timestamps produce a chain. Offline, build from the sorted array instead.
- Successor of the maximum, floor below the minimum. These have no answer; return
None/null/std::nullopt, not a sentinel like-1that could be a valid key. - Off-by-one in k-th. Decide whether is 0- or 1-indexed and check
1 <= k <= n. Rank conventions vary too ("number of keys < x" versus "≤ x");TreeMap.headMap(x).size()is "< x" and is , not , becauseTreeMapkeeps no subtree sizes. - Mutating keys in place. Changing a key already stored in a
TreeSet/std::setbreaks the invariant without the tree knowing. Remove, mutate, reinsert. The same goes for comparators that are not a strict weak ordering (NaN-containing floats).
Variations
- Self-balancing BSTs (AVL, red-black). Same invariant plus a balance rule enforced by rotations after every update, giving worst case. Next lesson: Balanced BSTs: AVL & Red-Black Trees.
- Treaps and randomized BSTs. Give each key a random priority and keep a heap order on priorities; the tree then has exactly the shape of a random BST regardless of insertion order, so the average-case analysis on this page becomes a guarantee in expectation. Splay trees move every accessed node to the root and achieve amortized. Skip lists replace the tree with randomized express lanes over a linked list. All three: Treaps, Splay Trees & Skip Lists.
- Scapegoat trees. No per-node balance data at all; when an insertion produces a path deeper than , find an ancestor whose subtree is too lopsided and rebuild it perfectly from its inorder sequence (this page's sorted-array build). amortized updates, worst-case lookups (Galperin & Rivest 1993; Andersson 1989).
- Order-statistic and augmented trees. Store any associative summary in each node (size, sum, max endpoint, min value) and maintain it on the update path. Size gives k-th and rank; max endpoint gives interval trees; sums give range sums. Segment trees and Fenwick trees are the array-indexed relatives for a fixed key universe.
- B-trees and B+-trees. Hundreds of keys per node, sized to a disk page; the same invariant between consecutive keys.
- Persistent BSTs. Copy only the root-to-change path on update and share the rest, keeping every past version; Haskell's
Data.Map(a weight-balanced tree) works this way. - Tries and radix trees. When keys are strings or bit strings, branch on characters instead of comparing whole keys; see Tries in Depth.
Practice ladder
Each problem is described in my own words. Solutions are Python and are run as part of this page's checks.
- Search in a Binary Search Tree (LeetCode 700) — Easy. Return the subtree rooted at a given key. Teaches the basic three-way descent, iteratively.
Hint
One loop: stop on equality or an empty pointer, otherwise move left or right by comparison.
- Range Sum of BST (LeetCode 938) — Easy. Sum all keys inside an inclusive range. Teaches pruning subtrees that cannot intersect the range.
Hint
Only descend left if the node's key is above the lower bound, and right if it is below the upper bound.
- Insert into a Binary Search Tree (LeetCode 701) — Medium. Insert a key that is guaranteed absent. Teaches "an unsuccessful search ends where the key belongs".
Hint
Walk down keeping the parent; attach a new leaf on the side where you fell off. Handle the empty tree.
- Convert Sorted Array to Binary Search Tree (LeetCode 108) — Easy. Build a height-balanced BST from sorted values. Teaches the middle-as-root recursion and the minimum-height build.
Hint
Root = middle element; left subtree from the left half, right subtree from the right half. The variant code above is a full solution.
- Validate Binary Search Tree (LeetCode 98) — Medium. Decide whether a binary tree satisfies the BST property. Teaches why parent-child checks are insufficient.
Hint
Pass an open interval down the recursion. Node values can equal the 32-bit extremes, so do not use them as sentinels.
Solution
from __future__ import annotations
from dataclasses import dataclass
from typing import Optional
@dataclass
class TreeNode:
val: int
left: Optional[TreeNode] = None
right: Optional[TreeNode] = None
def is_valid_bst(root: Optional[TreeNode]) -> bool:
stack: list[tuple[Optional[TreeNode], float, float]] = [(root, float("-inf"), float("inf"))]
while stack: # iterative: safe on deep trees
n, lo, hi = stack.pop()
if n is None:
continue
if not lo < n.val < hi:
return False
stack.append((n.left, lo, n.val))
stack.append((n.right, n.val, hi))
return True
assert is_valid_bst(TreeNode(2, TreeNode(1), TreeNode(3)))
assert not is_valid_bst(TreeNode(5, TreeNode(1), TreeNode(4, TreeNode(3), TreeNode(6))))
assert not is_valid_bst(TreeNode(10, TreeNode(5), TreeNode(15, TreeNode(6), TreeNode(20))))
assert is_valid_bst(TreeNode(2**31 - 1)) # extreme value is fine
assert not is_valid_bst(TreeNode(2, TreeNode(2))) # duplicates invalid
Time , space for the explicit stack (it can hold up to about $h + $ the number of pending right children, still worst case).
- Kth Smallest Element in a BST (LeetCode 230) — Medium. Return the k-th smallest key. Teaches early-stopping inorder, and the size-augmentation follow-up.
Hint
Iterative inorder; decrement on every pop. For the follow-up with frequent updates, store subtree sizes.
Solution
from __future__ import annotations
from dataclasses import dataclass
from typing import Optional
@dataclass
class TreeNode:
val: int
left: Optional[TreeNode] = None
right: Optional[TreeNode] = None
def kth_smallest(root: Optional[TreeNode], k: int) -> int:
stack: list[TreeNode] = []
cur = root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
k -= 1
if k == 0:
return cur.val
cur = cur.right
raise ValueError("k larger than tree size")
t = TreeNode(5, TreeNode(3, TreeNode(2, TreeNode(1)), TreeNode(4)), TreeNode(6))
assert [kth_smallest(t, k) for k in range(1, 7)] == [1, 2, 3, 4, 5, 6]
assert kth_smallest(TreeNode(3, TreeNode(1, None, TreeNode(2)), TreeNode(4)), 1) == 1
Time , space . With size-augmented nodes (the canonical implementation's kth), each query is .
- Lowest Common Ancestor of a Binary Search Tree (LeetCode 235) — Medium. Find the deepest node that has both given nodes as descendants. Teaches using the order to avoid a full-tree search.
Hint
Walk down from the root. If both keys are smaller go left, if both are larger go right; otherwise the current node is where their paths split, and that is the answer.
- Delete Node in a BST (LeetCode 450) — Medium. Remove a key and return the new root. Teaches the three cases and returning the new subtree root.
Hint
Recurse to the node. Zero or one child: return the other child. Two children: copy the successor's value in and delete the successor from the right subtree.
Solution
from __future__ import annotations
from dataclasses import dataclass
from typing import Optional
@dataclass
class TreeNode:
val: int
left: Optional[TreeNode] = None
right: Optional[TreeNode] = None
def delete_node(root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if root is None:
return None
if key < root.val:
root.left = delete_node(root.left, key)
elif key > root.val:
root.right = delete_node(root.right, key)
else:
if root.left is None:
return root.right
if root.right is None:
return root.left
s = root.right
while s.left:
s = s.left
root.val = s.val
root.right = delete_node(root.right, s.val)
return root
def inorder(n: Optional[TreeNode]) -> list[int]:
return inorder(n.left) + [n.val] + inorder(n.right) if n else []
def build() -> TreeNode:
return TreeNode(5, TreeNode(3, TreeNode(2), TreeNode(4)), TreeNode(6, None, TreeNode(7)))
r = delete_node(build(), 3)
assert inorder(r) == [2, 4, 5, 6, 7] and r.left.val == 4
r = delete_node(build(), 5) # root with two children
assert r.val == 6 and inorder(r) == [2, 3, 4, 6, 7]
assert inorder(delete_node(build(), 0)) == [2, 3, 4, 5, 6, 7]
assert delete_node(TreeNode(1), 1) is None
Time , space recursion.
- Binary Search Tree Iterator (LeetCode 173) — Medium. Implement sorted-order
nextandhasNextwith memory. Teaches the controlled inorder and amortized .
Hint
Keep a stack of the unvisited left spine. After popping a node, push its right child's left spine.
Solution
from __future__ import annotations
from dataclasses import dataclass
from typing import Optional
@dataclass
class TreeNode:
val: int
left: Optional[TreeNode] = None
right: Optional[TreeNode] = None
class BSTIterator:
def __init__(self, root: Optional[TreeNode]) -> None:
self.st: list[TreeNode] = []
self._spine(root)
def _spine(self, n: Optional[TreeNode]) -> None:
while n:
self.st.append(n)
n = n.left
def next(self) -> int:
n = self.st.pop()
self._spine(n.right)
return n.val
def hasNext(self) -> bool:
return bool(self.st)
it = BSTIterator(TreeNode(7, TreeNode(3), TreeNode(15, TreeNode(9), TreeNode(20))))
got = []
while it.hasNext():
got.append(it.next())
assert got == [3, 7, 9, 15, 20]
next is amortized (every node is pushed and popped once), worst case; memory .
- Two Sum IV – Input is a BST (LeetCode 653) — Easy. Decide whether two distinct nodes sum to a target. Teaches two pointers over a BST using a forward and a reverse iterator.
Hint
A hash set works in <span class="math" data-tex="O(n)"></span> space. The BST-native answer runs a smallest-first iterator and a largest-first iterator toward each other, as in [Two Pointers](/algorithms/linear/two-pointers), in <span class="math" data-tex="O(h)"></span> space.
- Trim a Binary Search Tree (LeetCode 669) — Medium. Remove all nodes outside a range while keeping relative structure. Teaches that a node out of range on the low side can be replaced by its trimmed right subtree.
Hint
If the node is below the range, return trim(right); if above, return trim(left); otherwise trim both children and return the node.
- Recover Binary Search Tree (LeetCode 99) — Medium. Two nodes' values were swapped; fix the tree without changing its shape. Teaches the inversion argument on the inorder sequence.
Hint
Track the previous node during inorder. On the first descent record both nodes; on a second descent update only the second. Swap the values at the end.
Solution
```python
from __future__ import annotations
from dataclasses import dataclass
from typing import Optional
@dataclass
class TreeNode:
val: int
left: Optional[TreeNode] = None
right: Optional[TreeNode] = None
def recover_tree(root: Optional[TreeNode]) -> None:
first = second = prev = None
stack: list[TreeNode] = []
cur = root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
if prev and prev.val > cur.val:
if first is None:
first = prev
second = cur # set on the first AND any later descent
prev, cur = cur, cur.right
assert first is not None and second is not None
first.val, second.val = second.val, first.val
def inorder(n: Optional[TreeNode]) -> list[int]:
return inorder(n.left) + [n.val] + inorder(n.right) if n else []
# The lesson's example tree with 30 and 65 swapped.
t = TreeNode(50, TreeNode(65, TreeNode(20), TreeNode(40, TreeNode(35), TreeNode(45))),
TreeNode(70, TreeNode(60, None, TreeNode(30)), TreeNode(80)))
recover_tree(t)
assert inorder(t) == [20, 30, 35, 40, 45, 50, 60, 65, 70, 80]
adj = TreeNode(2, TreeNode(3), TreeNode(1)) # non-adjacent: 3 and 1 swapped
recover_tree(adj)
assert inorder(adj) == [1, 2, 3]
one = TreeNode(1, None, TreeNode(2, TreeNode(3))) # inorder 1 3 2: adjacent swap
recover_tree(one)
assert inorder(one) == [1, 2, 3]
```
Time <span class="math" data-tex="O(n)"></span>, space <span class="math" data-tex="O(h)"></span>. LeetCode's follow-up asks for <span class="math" data-tex="O(1)"></span> space: replace the stack with Morris traversal.
- Unique Binary Search Trees (LeetCode 96) — Medium. Count structurally distinct BSTs on keys . Teaches the root-split recursion that also drives the random-BST analysis; the answer is the Catalan number (5 for , 16,796 for ).
Hint
Choosing root <span class="math" data-tex="r"></span> leaves <span class="math" data-tex="r - 1"></span> keys on the left and <span class="math" data-tex="n - r"></span> on the right, independently. Sum the products over <span class="math" data-tex="r"></span>; memoise.
- Concert Tickets (CSES 1091) — Medium. Each customer, in order, takes the most expensive remaining ticket not above their budget. Teaches floor queries with deletion on a multiset.
Hint
In C++ use `std::multiset`: `upper_bound(budget)`, step back once, erase that iterator. In Java use a `TreeMap<price, count>` with `floorKey`. In Python, sort the prices and use a union-find "next available to the left" pointer to simulate deletions in near-linear time.
- Contains Duplicate III (LeetCode 220) — Hard. Decide whether two indices within distance hold values within distance . Teaches a sliding window over an ordered set: for each new value, a ceiling query answers "is there a value in ?".
Hint
Keep the last <span class="math" data-tex="k"></span> values in an ordered set; for each <span class="math" data-tex="x"></span>, check `ceiling(x - t) <= x + t`, then insert <span class="math" data-tex="x"></span> and evict the value that left the window. An <span class="math" data-tex="O(n)"></span> alternative buckets values by `x // (t + 1)`.
Common mistakes & interview follow-ups
Mistakes interviewers see constantly:
- The validation, sentinel-bound and root-reassignment bugs from Pitfalls, and collapsing delete into two cases.
- Saying "BST operations are " without the word balanced. The honest answer is .
Follow-ups and short answers:
- "What if the tree is modified often and k-th smallest is queried often?" Augment each node with its subtree size, maintained on insert and delete; k-th and rank become , and on a balanced tree.
- "What is the worst case and when does it happen?" per operation, when keys arrive sorted or nearly sorted. Fix with a self-balancing tree, randomisation (treap), or an offline sorted-array build.
- "Validate in extra space?" Morris inorder traversal with a
prevvalue; it temporarily rewires and then restores right pointers. - "Why not a hash table?" It cannot answer floor, successor, range or k-th without scanning; for pure lookup, use one.
- "How would you store a BST on disk?" Not as a binary tree (each level is a random I/O): use a B+-tree whose node fills a page, height 3 or 4 for millions of keys.
- "Count smaller elements after each position?" Insert from right to left into an order-statistic tree and ask
rankbefore each insert. with a balanced tree; a Fenwick tree over compressed values does the same with smaller constants.
Quick quiz
- Why does the inorder traversal of a BST produce sorted output, and how does that fact give an , -space validator?
Answer
By induction: inorder emits the left subtree's keys (all smaller than the root, and sorted by the hypothesis), then the root, then the right subtree's keys (all larger, sorted). Conversely a strictly increasing inorder sequence implies the BST property. So validate by running an iterative inorder and checking each key exceeds the previous one; the only state is the stack () and prev.
- You delete a node with two children by copying its successor's key into it. Why does the successor have at most one child, and why does the tree stay a BST?
Answer
The successor is the minimum of the right subtree, found by going left until you cannot, so it has no left child. Its key is larger than everything in the left subtree (which was smaller than the deleted key) and smaller than everything else in the right subtree (it was the minimum), so placing it at the deleted node satisfies the property on both sides; removing it from the right subtree is a zero- or one-child deletion.
- Inserting the keys 1 to 1,000 in increasing order: what is the height and how many comparisons does the build make?
Answer
Height 999 (a right-leaning chain). The i-th insertion compares against all existing keys, so the total is comparisons.
- What is the expected average node depth of a BST built from a random permutation of keys, and roughly how does it compare with a perfectly balanced tree?
Answer
Exactly . A perfectly balanced tree has average depth about , so a random BST is roughly 39% deeper on average: about 24.8 versus 19 for a million keys. The height is larger, around asymptotically (Devroye 1986), measured at about 48 for a million keys.
Further reading / sources
- Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4th ed., Chapter 12 "Binary Search Trees" (search, successor, insertion, transplant-based deletion; the 3rd edition's §12.4 covers randomly built trees) and §17.1 "Dynamic order statistics" (§14.1 in the 3rd edition).
- Sedgewick & Wayne, Algorithms, 4th ed., §3.2 "Binary Search Trees" — rank/select via subtree sizes, Hibbard deletion and its long-run imbalance, and the average-case analysis.
- Knuth, The Art of Computer Programming, Vol. 3, 2nd ed., §6.2.2 "Binary Tree Searching" — exact average costs of random BSTs and the history of the method.
- T. N. Hibbard, "Some combinatorial properties of certain trees with applications to searching and sorting", Journal of the ACM 9(1), 1962.
- L. Devroye, "A note on the height of binary search trees", Journal of the ACM 33(3), 1986 — the height constant.
- B. Reed, "The height of a random binary search tree", Journal of the ACM 50(3), 2003 — the second-order term and bounded variance.
- J. L. Eppinger, "An empirical study of insertion and deletion in binary search trees", Communications of the ACM 26(9), 1983.
- I. Galperin & R. L. Rivest, "Scapegoat trees", SODA 1993.
- Oracle,
java.util.TreeMapJavadoc ("A Red-Black tree based NavigableMap implementation"); cppreference,std::mapandstd::map::lower_bound; Grant Jenks, Sorted Containers documentation (implementation notes on the list-of-lists design).
Prev: Tree Problem Patterns · Next: Balanced BSTs: AVL & Red-Black Trees
Related: Module 3 — Trees · Trees (Overview) · Binary Trees & Traversals · Binary Search Mastery · Quick Sort · Quickselect & Order Statistics · Hash Tables · Indexing Deep Dive · Storage Engines · DSA: Zero to Mastery