On this page

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 statementUse 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 BSTInorder 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 BSTFirst 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.

Start at the root. Compare, then go left, go right, or stop.

Trace: search for 65, then for 42.

StepTargetNodeComparisonNext
1655065 > 50right
2657065 < 70left
3656065 > 60right
46565equalfound after 4 comparisons
1425042 < 50left
2423042 > 30right
3424042 > 40right
4424542 < 45left 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).

StepDeleteNode foundCaseActionInorder afterwards
120leaf under 30130.left = empty30 35 40 45 50 60 65 70 80
260only right child 65270.left = 6530 35 40 45 50 65 70 80
350root, children 30 and 703successor: right to 70, left to 65, 65.left empty, so s = 65
4copy 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 .

  1. Every key in is , so is still a valid left subtree of a node holding .
  2. 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 .
  3. 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.
  4. 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.

StepNodeCompareCandidateMove
15040 < 5050left
23040 ≥ 3050right
34040 ≥ 4050right
44540 < 4545left, 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).

xNodeRelationFloor so farCeiling so farMove
425050 > 42–50left
423030 < 423050right
424040 < 424050right
424545 > 424045left, empty: stop
635050 < 6350–right
637070 > 635070left
636060 < 636070right
636565 > 636065left, 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).

StepNodesize(left)kDecision
150577 > 6: go right, k = 7 − 6 = 1
270211 ≤ 2: go left
360011 = 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 :

PositionPairInversion?firstsecond
020, 65no––
165, 35yes6535
2–635 … 60no6535
760, 30yes6530
830, 70no6530

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.

ProblemRungTimeExtra spaceWhy it improves
Validatemax/min of subtrees per node worst—
Validateinorder into arraylemma: global order becomes adjacent pairs
Validatebounds / prevcarries ancestors' constraints, no array, early exit
k-thcollect + sort—
k-thfull inorderinorder is already sorted
k-thinorder, stop at ktouches only the first k keys
k-thsize-augmented integers total, per nodeskips 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

OperationTimeNotes
search, insert, deleteone 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 walkeach 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 arrayminimum 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):

ntrialsmean heightmean depthexact
1,00020021.029.826.011.0010.9910.0
10,0005029.939.735.415.5315.5813.3
100,0001039.949.644.920.1420.1816.6
1,000,000347.759.654.424.5124.7919.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 contains first; 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::map and TreeMap instead 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.

OperationJava TreeMap / TreeSetC++ std::map / std::setPythonTypeScript / JavaScript
structurered-black treered-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 / ceilingfloorKey, ceilingKeyprev(upper_bound(x)), lower_bound(x)SortedList.bisect_right, bisect_leftwrite it (sorted array + binary search, or a tree library)
strict successor / predecessorhigherKey, lowerKeyupper_bound(x), prev(lower_bound(x))bisect_right, bisect_left − 1—
range viewsubMap, headMap, tailMap (live views)iterate [lower_bound(lo), upper_bound(hi))irange(lo, hi)—
k-th smallestnot supported (iterate)not supported in std; GNU __gnu_pbds::tree with tree_order_statistics_node_update has find_by_order / order_of_keySortedList[k]—
min / max / popfirstKey, lastKey, pollFirstEntrybegin(), 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 TreeMap and TreeSet are red-black trees (the Javadoc says so and credits CLRS); ConcurrentSkipListMap is the concurrent ordered alternative. C++'s std::map, std::set, std::multimap and std::multiset are 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 k on 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_MIN and using strict comparisons rejects a valid tree that contains that exact value. Use long bounds, 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 -1 that 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 , because TreeMap keeps no subtree sizes.
  • Mutating keys in place. Changing a key already stored in a TreeSet/std::set breaks 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.

  1. 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.

  1. 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.

  1. 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.

  1. 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.

  1. 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).

  1. 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 .

  1. 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.

  1. 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.

  1. Binary Search Tree Iterator (LeetCode 173) — Medium. Implement sorted-order next and hasNext with 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 .

  1. 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.
  1. 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.
  1. 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.
  1. 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.
  1. 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.
  1. 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 prev value; 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 rank before each insert. with a balanced tree; a Fenwick tree over compressed values does the same with smaller constants.

Quick quiz

  1. 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.

  1. 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.

  1. 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.

  1. 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.TreeMap Javadoc ("A Red-Black tree based NavigableMap implementation"); cppreference, std::map and std::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