10 — Trees

A tree is a connected graph with no cycles. Pick one vertex as the root and every other vertex gets exactly one parent, the neighbor on its path to the root. That single fact drives almost everything in this chapter: because there is exactly one path between any two nodes, a tree can be processed by recursion on subtrees, and every subtree is itself a tree.

Trees show up as file systems, the DOM, syntax trees in a compiler, decision trees, organizational charts, and, most importantly for performance, as search trees: binary search trees, AVL and red-black trees in language libraries and kernels, and B-trees in every serious database. The second half of this chapter covers those, because a search tree is only useful if its height stays logarithmic, and keeping it there is the hard part.

Tries, segment trees, Fenwick trees and the other range structures are in chapter 11. Heaps, which are trees stored in arrays, are in chapter 9. Timings in this chapter were measured with Python 3.14 on one Mac; exact numbers will differ elsewhere, and the ratios are what matter.

Vocabulary

Most of the terms are standard, but sources disagree on a few, so this chapter fixes its conventions here.

Some books count height in nodes instead of edges, so a single node has height 1. Both are fine; mixing them is the usual source of off-by-one errors. The code below returns heights in edges unless a comment says otherwise.

A binary tree limits each node to at most two children, called left and right. The distinction matters: a node with only a left child is a different tree from a node with only a right child. The number of distinct binary tree shapes with $n$ nodes is the Catalan number $C_n = \frac{1}{n+1}\binom{2n}{n}$, which is 1, 1, 2, 5, 14, 42 for $n = 0 \ldots 5$.

Four shape properties come up repeatedly, and they are often confused:

A perfect tree is both full and complete. A complete tree need not be full (its last internal node may have one child), and a full tree need not be complete. The minimum height of any binary tree with $n$ nodes is $\lfloor \log_2 n \rfloor$, reached by a complete tree, and the maximum is $n - 1$, reached by a chain.

Representations

Linked nodes. Each node holds a value and two pointers. This is the default, and the one used throughout this chapter:

class Node:
    __slots__ = ("val", "left", "right")

    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

__slots__ fixes the attribute set and stores the fields in the object itself. Allocating 100,000 nodes with integer values measured 96 bytes per node with __slots__ and 136 without it.

The code in this chapter assumes from collections import deque, defaultdict and import struct where it uses them.

Implicit array. Store the root at index 0; the children of index $i$ are at $2i + 1$ and $2i + 2$ and the parent is at $\lfloor (i - 1)/2 \rfloor$. No pointers at all, and excellent cache behavior, but it only stays compact for complete trees. A chain of $n$ nodes would need $2^n$ slots. Heaps and segment trees use this layout.

Parent array. parent[v] for each node, with the root pointing to itself or −1. This is what many problems give as input, and what binary lifting (below) builds on. It answers “who is my parent” in $O(1)$ and “who are my children” only after building a child list.

Adjacency list. For a general (unrooted, or arbitrary-degree) tree, store each node’s neighbors. Any node can serve as the root, and the tree algorithms become graph algorithms with a parent argument to avoid walking back up.

Left-child, right-sibling. Any N-ary tree can be stored as a binary tree: the left pointer goes to the first child, the right pointer to the next sibling. This is how some file systems and compilers store variable-arity trees with fixed-size nodes.

Many test cases, including LeetCode’s, describe a tree as a level-order list with None for missing children: [1, 2, 3, None, 4] means 1 has children 2 and 3, 2 has no left child and a right child 4. The examples below use a build function that reads that format.

Depth-first traversals

A traversal visits every node once. Depth-first traversals go as deep as possible before backtracking, and the three classic orders differ only in when the node itself is visited relative to its two subtrees.

              1
            /   \
           2     3
          / \     \
         4   5     6
            / \
           7   8

Each order has a natural use. Preorder visits a parent before its children, so it is the order for copying a tree, for serializing one (the root comes first, so a reader can build top-down), and for printing an indented outline. Inorder on a binary search tree yields the keys in sorted order, which is the basis of BST validation, kth smallest, and range queries. Postorder visits children before the parent, which is what any computation that combines subtree results needs: heights, sizes, freeing memory, evaluating an expression tree.

Recursive

The recursive versions are three lines each and differ only in where the append goes:

def inorder_rec(root, out=None):
    if out is None:
        out = []
    if root:
        inorder_rec(root.left, out)
        out.append(root.val)
        inorder_rec(root.right, out)
    return out

Time is $O(n)$, and space is $O(h)$ for the call stack, where $h$ is the height. That is $O(\log n)$ for a balanced tree and $O(n)$ for a chain. CPython’s default recursion limit is 1,000 frames, so a recursive traversal of a degenerate tree of a few thousand nodes raises RecursionError. Raising the limit with sys.setrecursionlimit moves the problem rather than solving it; deep enough recursion can crash the interpreter. For input that might be a long chain, use one of the iterative versions.

Iterative

Preorder is the easiest: pop a node, visit it, push its right child and then its left child, so the left is popped first.

def preorder_iter(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:
            stack.append(node.right)   # pushed first, popped second
        if node.left:
            stack.append(node.left)
    return out

Inorder needs the stack to hold the path of nodes whose left subtree is in progress. Walk left as far as possible, pushing every node; pop one, visit it, then move to its right subtree and repeat.

def inorder_iter(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:                    # walk left, remembering the path
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out

Postorder is the awkward one, because a node on top of the stack may be visited only after its right subtree is finished. Tracking the last node emitted answers the question “did I just come back from the right?”:

def postorder_iter(root):
    out, stack = [], []
    node, last = root, None
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        top = stack[-1]
        if top.right and top.right is not last:
            node = top.right           # right subtree not done yet
        else:
            out.append(top.val)
            last = stack.pop()
    return out

A common shortcut computes “node, right, left” with the preorder loop and reverses the result. It produces the right sequence but holds all $n$ values before returning anything, so it cannot be used to process nodes as they finish (for example to free them).

All three iterative versions are $O(n)$ time and $O(h)$ space. They were checked against the recursive versions on 3,000 random trees.

Morris inorder traversal

Both versions above use $O(h)$ extra memory for a stack. Joseph Morris’s 1979 traversal uses $O(1)$: it temporarily rewires the tree so the tree itself remembers the way back up.

The idea

In an inorder traversal, after finishing a node’s left subtree, the next node to visit is the node itself. The last node visited in that left subtree is the node’s inorder predecessor: the rightmost node of the left subtree. That predecessor always has an empty right pointer (otherwise it would not be rightmost). Morris uses that empty pointer as a temporary thread back to the current node.

At each node cur:

1. If cur has no left child, visit it and move right. (The “right” may be a real child or a thread.)
2. Otherwise find the predecessor: step left once, then right until the right pointer is empty or points back to cur.
3. If the predecessor’s right pointer is empty, this is the first arrival at cur. Set the thread pred.right = cur and move left.
4. If the predecessor’s right pointer is cur, the thread was followed, so the left subtree is finished. Remove the thread, visit cur, and move right.

def morris_inorder(root):
    out, cur = [], root
    while cur:
        if cur.left is None:
            out.append(cur.val)
            cur = cur.right
        else:
            pred = cur.left
            while pred.right and pred.right is not cur:
                pred = pred.right
            if pred.right is None:      # first visit: make the thread
                pred.right = cur
                cur = cur.left
            else:                       # second visit: remove the thread
                pred.right = None
                out.append(cur.val)
                cur = cur.right
    return out

Step by step

On a perfect BST of seven nodes:

            4
          /   \
         2     6
        / \   / \
       1   3 5   7

An instrumented copy of the loop printed each decision:

at 4: predecessor 3, add thread 3->4, go left
at 2: predecessor 1, add thread 1->2, go left
at 1: no left child, visit 1, go right
at 2: thread 1->2 found, remove it, visit 2, go right
at 3: no left child, visit 3, go right
at 4: thread 3->4 found, remove it, visit 4, go right
at 6: predecessor 5, add thread 5->6, go left
at 5: no left child, visit 5, go right
at 6: thread 5->6 found, remove it, visit 6, go right
at 7: no left child, visit 7, go right
[1, 2, 3, 4, 5, 6, 7]

The step “at 1 … go right” follows the thread 1→2, and “at 3 … go right” follows 3→4. After the traversal every thread has been removed, and the tree is exactly as it was.

Cost and caveats

Time is $O(n)$, though that is not obvious because of the inner predecessor search. Each node with a left child triggers two predecessor searches (one to create the thread, one to find it), and each search walks the right spine of that node’s left subtree. Every edge of the tree lies on at most one such spine, so the total walking is at most about $2n$ edges, and the whole traversal does a constant amount of work per edge.

Measured on a random BST of 200,000 nodes (best of seven runs):

Morris trades a constant factor of time for memory. In Python the trade is rarely worth it; in C with very deep trees and no spare memory, it can be.

The pitfalls are all about the temporary modification:

• The tree is not read-only during the traversal. Another thread reading the tree concurrently sees cycles. Morris is unsafe on shared structures without exclusive access.
• Stopping early leaves threads behind. A “kth smallest” that returns as soon as it finds the answer will leave the tree with cycles in it. Either finish the loop to clean up, or do not use Morris for early-exit searches.
• Exceptions mid-traversal have the same effect as stopping early.

The preorder variant differs in one line: emit cur when the thread is created rather than when it is removed. Postorder is possible but considerably more involved (it reverses right spines in place), and is rarely worth it.

Breadth-first traversals

Level order

Level order visits the tree one depth at a time using a queue (breadth-first search, covered in general in chapter 12). Taking len(q) at the start of each round gives exactly the nodes of the current level, which is how most level-based problems separate one level from the next:

def level_order(root):
    if not root:
        return []
    out, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):        # exactly the nodes of this level
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        out.append(level)
    return out

Time $O(n)$; space $O(w)$ where $w$ is the maximum width. For a perfect tree the last level holds about half the nodes, so the queue can reach $n/2$, more than the $O(\log n)$ a DFS needs on the same tree. On a chain it is the reverse: BFS needs $O(1)$ and DFS needs $O(n)$. Use collections.deque; list.pop(0) is $O(n)$ per call and turns the traversal quadratic.

Zigzag

Binary Tree Zigzag Level Order Traversal alternates direction per level. The cleanest version collects each level normally and reverses every other one; reversing costs $O(w)$ per level and $O(n)$ total. A deque that appends to the left on odd levels does the same without the reversal step.

def zigzag(root):
    return [lvl if i % 2 == 0 else lvl[::-1]
            for i, lvl in enumerate(level_order(root))]

On the example tree: [[1], [3, 2], [4, 5, 6], [8, 7]].

Positional traversals and views

The next group of problems places each node on a grid: the root at row 0, column 0; a left child at (row + 1, column − 1); a right child at (row + 1, column + 1). On the example tree:

column:   -2   -1    0    1    2
row 0:               1
row 1:          2         3
row 2:     4         5         6
row 3:          7         8

Vertical order

Vertical Order Traversal of a Binary Tree (LeetCode 987) lists the columns left to right, each top to bottom, with ties at the same row and column broken by value. Collecting (column, row, value) triples and sorting them handles all three rules at once:

def vertical_order(root):
    """Columns left to right; inside a column, by row, then by value."""
    cells = []
    stack = [(root, 0, 0)] if root else []
    while stack:
        node, row, col = stack.pop()
        cells.append((col, row, node.val))
        if node.left:
            stack.append((node.left, row + 1, col - 1))
        if node.right:
            stack.append((node.right, row + 1, col + 1))
    cells.sort()
    cols = defaultdict(list)
    for col, _, val in cells:
        cols[col].append(val)
    return [cols[c] for c in sorted(cols)]

Result: [[4], [2, 7], [1, 5], [3, 8], [6]]. The sort makes it $O(n \log n)$. An older variant of the problem (LeetCode 314) breaks same-cell ties by left-to-right BFS order instead of value; the BFS version with a dictionary of lists, plus tracking the min and max column, solves that one in $O(n)$.

Top, bottom, left and right views

• Left view: the first node of each level. On the example: [1, 2, 4, 7].
• Right view (Binary Tree Right Side View): the last node of each level: [1, 3, 6, 8].
• Top view: for each column, the node with the smallest row. Doing BFS guarantees the first node seen in a column is the topmost: [4, 2, 1, 3, 6].
• Bottom view: for each column, the node with the largest row. With BFS, the last node seen in a column wins: [4, 7, 5, 8, 6].

def _column_view(root, keep_first):
    seen = {}
    q = deque([(root, 0)]) if root else deque()
    while q:
        node, col = q.popleft()
        if not keep_first or col not in seen:
            seen[col] = node.val        # BFS order: first = top, last = bottom
        if node.left:
            q.append((node.left, col - 1))
        if node.right:
            q.append((node.right, col + 1))
    return [seen[c] for c in sorted(seen)]

Two nodes can share a row and a column (for example the right child of a left child and the left child of a right child of the same node). The views are then ambiguous, and the common convention is the one this code implements: for the bottom view the later node in level order (the one further right) wins. A DFS version must carry the row and compare it explicitly, because DFS does not visit in row order. All views are $O(n)$ apart from sorting the column keys, which can be avoided by tracking the minimum column and indexing from it.

Boundary traversal

Boundary of Binary Tree (LeetCode 545) lists, counterclockwise from the root: the root, the left boundary top-down, all leaves left to right, and the right boundary bottom-up, with no node repeated. The left boundary is the path that goes left when possible and right otherwise, starting at the root’s left child and excluding leaves; the right boundary mirrors it.

def boundary(root):
    if not root:
        return []

    def is_leaf(n):
        return n.left is None and n.right is None

    out = [root.val]
    if is_leaf(root):
        return out
    node = root.left                    # left edge, top down, no leaves
    while node:
        if not is_leaf(node):
            out.append(node.val)
        node = node.left if node.left else node.right
    stack = [root]                      # leaves, left to right
    while stack:
        n = stack.pop()
        if is_leaf(n) and n is not root:
            out.append(n.val)
        if n.right:
            stack.append(n.right)
        if n.left:
            stack.append(n.left)
    right, node = [], root.right        # right edge, collected then reversed
    while node:
        if not is_leaf(node):
            right.append(node.val)
        node = node.right if node.right else node.left
    out.extend(reversed(right))
    return out

On the example tree the result is [1, 2, 4, 7, 8, 6, 3]. The edge cases are where implementations fail: a root with no left child has an empty left boundary (the right subtree’s nodes do not count), the root must not be counted as a leaf, and a leaf that is also at the end of a boundary path must appear only once, in the leaves section. This implementation passes both of the problem’s published examples.

Height, diameter and path sums

Most tree problems are postorder computations: each node combines answers from its children and passes one number up. The trick in the harder ones is that the value passed up differs from the answer being tracked.

Height

def height(root):
    """Height in edges: empty tree -1, single node 0."""
    if root is None:
        return -1
    return 1 + max(height(root.left), height(root.right))

$O(n)$ time, $O(h)$ stack. Counting levels in a BFS gives the same answer without recursion.

Diameter

The diameter is the number of edges on the longest path between any two nodes (Diameter of Binary Tree, LeetCode 543). The longest path has a highest node, and at that node it goes down into the left subtree as deep as possible and down into the right subtree as deep as possible. So for every node, the candidate is (left height in nodes) + (right height in nodes), and the answer is the maximum over all nodes. What a node returns to its parent is different: only one branch can continue upward, so it returns $1 + \max(\text{left}, \text{right})$.

def diameter(root):
    best = 0

    def depth(node):                    # returns height in nodes
        nonlocal best
        if node is None:
            return 0
        l, r = depth(node.left), depth(node.right)
        best = max(best, l + r)         # edges on the path through node
        return 1 + max(l, r)

    depth(root)
    return best

On the example tree the diameter is 5 (the path 7–5–2–1–3–6). The path need not pass through the root, which is the most common wrong assumption. Computing height(left) + height(right) separately at every node is $O(n^2)$ on a chain; the single pass above is $O(n)$. For a general unrooted tree, two BFS passes also work: the farthest node from any start is one end of a diameter, and the farthest node from that is the other end.

Path sums

Three versions of the problem need three different techniques.

Root-to-leaf, exists (Path Sum, LeetCode 112). Subtract each value from the target on the way down; check at a leaf. The check must be at a leaf, not at None: a node with one child is not the end of a root-to-leaf path.

def has_path_sum(root, target):
    if root is None:
        return False
    if root.left is None and root.right is None:
        return root.val == target
    rest = target - root.val
    return has_path_sum(root.left, rest) or has_path_sum(root.right, rest)

Root-to-leaf, list them (Path Sum II). Same recursion with a path list, appending on the way down and popping on the way back (backtracking, chapter 15). Copy the path when recording an answer.

Any downward path (Path Sum III, LeetCode 437). A path may start and end anywhere as long as it goes downward. Checking every start node is $O(n h)$, which is $O(n^2)$ on a chain. The linear solution is the prefix-sum technique from chapter 4 applied to the root-to-node path: if the running sum from the root is $S$ and some ancestor’s running sum was $S - \text{target}$, the path between them sums to the target. A dictionary counts the running sums on the current root path, incremented on the way down and decremented on the way back up so that sibling branches do not see each other’s sums.

def path_sum_count(root, target):
    """Number of downward paths (any start, any end) summing to target."""
    prefix = defaultdict(int)
    prefix[0] = 1

    def dfs(node, running):
        if node is None:
            return 0
        running += node.val
        count = prefix[running - target]
        prefix[running] += 1
        count += dfs(node.left, running) + dfs(node.right, running)
        prefix[running] -= 1            # undo on the way back up
        return count

    return dfs(root, 0)

On LeetCode’s example [10, 5, -3, 3, 2, None, 11, 3, -2, None, 1] with target 8 it returns 3. The prefix[0] = 1 entry represents the empty prefix above the root, so paths that start at the root are counted.

Maximum path sum

Binary Tree Maximum Path Sum (LeetCode 124) asks for the largest sum along any path, where values may be negative and the path need not include the root or a leaf. It is the diameter pattern again, weighted:

• At each node, the best path that peaks here is node.val + left_gain + right_gain, where a gain below zero is replaced by zero (a negative branch is better left off).
• The value returned upward is the best path that ends here and can be extended by the parent: node.val + max(left_gain, right_gain). A path cannot fork, so only one branch goes up.

def max_path_sum(root):
    best = float("-inf")

    def gain(node):
        nonlocal best
        if node is None:
            return 0
        l = max(gain(node.left), 0)     # drop a negative branch
        r = max(gain(node.right), 0)
        best = max(best, node.val + l + r)
        return node.val + max(l, r)     # a path can only go one way up

    gain(root)
    return best

On [-10, 9, 20, None, None, 15, 7] it returns 42 (15 + 20 + 7). The two classic bugs: initializing best to 0, which is wrong when every value is negative (the answer is then the largest single value), and clamping the returned value at zero inside the node itself rather than at the parent, which would let a path consist of nothing. Both diameter and maximum path sum were checked against an exhaustive search over all pairs of nodes on random trees with negative values.

Lowest common ancestor and distance

The lowest common ancestor (LCA) of nodes $p$ and $q$ is the deepest node that has both as descendants, where a node counts as its own descendant. It is the meeting point of their paths to the root, and the basis of distance queries, of many path problems, and of version-control merge bases (on a DAG rather than a tree, but the same idea).

In a binary tree

Lowest Common Ancestor of a Binary Tree (LeetCode 236). Recurse into both subtrees. A subtree returns $p$ or $q$ if it contains one of them, the LCA if it contains both, and None otherwise. The first node where both sides report something is the LCA.

def lca(root, p, q):
    """p and q are Node objects known to be in the tree."""
    if root is None or root is p or root is q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root
    return left or right

$O(n)$ time. The early return when root is p is correct only because both nodes are known to be present: if $q$ is below $p$, then $p$ is the answer and there is no need to look further. If either node might be absent, the function returns a wrong non-None answer; the fix is to count how many of the two were actually found and only trust the result when the count is 2.

In a binary search tree

Lowest Common Ancestor of a BST (LeetCode 235). The ordering does the work: if both keys are smaller than the current node, the LCA is in the left subtree; if both are larger, the right; otherwise the paths split here, and this node is the LCA.

def lca_bst(root, a, b):
    node = root
    while node:
        if a < node.val and b < node.val:
            node = node.left
        elif a > node.val and b > node.val:
            node = node.right
        else:
            return node

$O(h)$ time, $O(1)$ space.

Distance between two nodes

The path from $p$ to $q$ goes up to their LCA and down again, so

$\text{dist}(p, q) = \text{depth}(p) + \text{depth}(q) - 2\,\text{depth}(\text{lca}(p, q))$

With an $O(n)$ LCA and depth search that is $O(n)$ per query. Many queries on one tree need the preprocessing below. (A related problem, All Nodes Distance K in Binary Tree, is easier to treat as a graph: record each node’s parent, then BFS from the target for $k$ steps.)

Binary lifting

The recursive LCA costs $O(n)$ per query. For a tree that is queried many times, binary lifting preprocesses in $O(n \log n)$ and answers each LCA or “$k$th ancestor” query in $O(\log n)$.

The table

Store, for every node $v$ and every $k$ up to $\log_2 n$, the node $2^k$ steps above $v$:

$\text{up}[0][v] = \text{parent}(v), \qquad \text{up}[k][v] = \text{up}[k-1][\,\text{up}[k-1][v]\,]$

The recurrence says that jumping $2^k$ is jumping $2^{k-1}$ twice. The root’s parent is set to the root itself, so jumps past the top stay at the root.

$k$th ancestor. Write $k$ in binary and take the jump for each set bit. $13 = 8 + 4 + 1$, so three table lookups climb 13 levels.

LCA. First lift the deeper node to the same depth as the shallower. If they are now equal, that is the LCA. Otherwise, for $k$ from large to small, jump both nodes by $2^k$ whenever their $2^k$-th ancestors differ. Jumping only when the ancestors differ keeps both nodes strictly below the LCA, and trying every power from the largest down lands them exactly one level below it, so the answer is their parent. This is binary search on the depth of the LCA.

class BinaryLifting:
    def __init__(self, n, parent, root=0):
        """parent[v] is v's parent; parent[root] is ignored."""
        self.LOG = max(1, n.bit_length())
        children = [[] for _ in range(n)]
        for v in range(n):
            if v != root:
                children[parent[v]].append(v)
        self.depth = [0] * n
        up = [root] * n
        order = [root]                     # BFS so parents come first
        for v in order:
            for c in children[v]:
                self.depth[c] = self.depth[v] + 1
                up[c] = v
                order.append(c)
        self.up = [up]                     # up[k][v] = 2^k-th ancestor of v
        for k in range(1, self.LOG):
            prev = self.up[-1]
            self.up.append([prev[prev[v]] for v in range(n)])

    def kth_ancestor(self, v, k):
        if k > self.depth[v]:
            return -1
        bit = 0
        while k:
            if k & 1:
                v = self.up[bit][v]
            k >>= 1
            bit += 1
        return v

    def lca(self, a, b):
        if self.depth[a] < self.depth[b]:
            a, b = b, a
        a = self.kth_ancestor(a, self.depth[a] - self.depth[b])
        if a == b:
            return a
        for k in range(self.LOG - 1, -1, -1):
            if self.up[k][a] != self.up[k][b]:
                a, b = self.up[k][a], self.up[k][b]
        return self.up[0][a]

    def dist(self, a, b):
        return self.depth[a] + self.depth[b] - 2 * self.depth[self.lca(a, b)]

Worked example

            0
          /   \
         1     2
        / \     \
       3   4     5
       |
       6
       |
       7

up[0] = [0, 0, 0, 1, 1, 2, 3, 6]
up[1] = [0, 0, 0, 0, 0, 0, 1, 3]
up[2] = [0, 0, 0, 0, 0, 0, 0, 0]
up[3] = [0, 0, 0, 0, 0, 0, 0, 0]
kth_ancestor(7, 3) = 1
lca(7, 4) = 1  lca(7, 5) = 0
dist(7, 5) = 6

For lca(7, 4): node 7 is at depth 4 and node 4 at depth 2, so 7 is lifted by 2 using up[1][7] = 3. Now 3 and 4 differ. From the top power down, up[k][3] and up[k][4] are equal (both 0 or both 1) for every $k$, so neither jumps, and the answer is up[0][3] = 1.

The implementation was checked against walking parent pointers on 300 random trees of up to 300 nodes, with shuffled labels so the root was not always 0. Kth Ancestor of a Tree Node (LeetCode 1483) is exactly the kth_ancestor method.

Alternatives

Serializing a tree

To store a tree in a file or send it over a network it has to become a flat sequence that can be turned back into exactly the same tree (Serialize and Deserialize Binary Tree, LeetCode 297). The difficulty is that a list of values alone does not determine the shape: the preorder 1 2 3 matches five different trees. Some extra information must record where the children are missing.

(For trees with distinct values, preorder plus inorder together do determine the tree, as do postorder plus inorder. Preorder plus postorder do not, unless the tree is full.)

Preorder with null markers

Write the preorder, with a marker such as # for every empty child. The reader consumes tokens in the same recursive order: a value creates a node and then reads its left and right subtrees; a # returns nothing.

def serialize_pre(root):
    out = []

    def go(node):
        if node is None:
            out.append("#")
            return
        out.append(str(node.val))
        go(node.left)
        go(node.right)

    go(root)
    return ",".join(out)


def deserialize_pre(data):
    tokens = iter(data.split(","))

    def go():
        tok = next(tokens)
        if tok == "#":
            return None
        node = Node(int(tok))
        node.left = go()
        node.right = go()
        return node

    return go()

For the tree with root 1, left child 2, and right child 3 whose children are 4 and 5:

'1,2,#,#,3,4,#,#,5,#,#'

A binary tree with $n$ nodes has exactly $n + 1$ empty child slots, so the output has $2n + 1$ tokens. The format is self-delimiting: the reader knows when each subtree ends without any lengths.

Level order

BFS order with # markers, trailing markers dropped. This is LeetCode’s own format, and it is the more readable one for wide, shallow trees:

'1,2,3,#,#,4,5'

Deserialization reads values in order and assigns them as the children of nodes taken from a queue, which is the build function used throughout this chapter. Both formats are $O(n)$ in time and space, and neither needs recursion to read if written with an explicit stack or queue.

A custom binary encoding

Text formats spend most of their bytes on separators and markers. A compact alternative writes each node in preorder as one flag byte (bit 0: has a left child, bit 1: has a right child) followed by the value as a fixed-width integer. The flags replace all the null markers.

def encode_compact(root):
    """Preorder; each node is one flag byte (bit0 = has left, bit1 = has right)
    followed by its value as a 4-byte signed little-endian int."""
    out = bytearray()
    stack = [root] if root else []
    while stack:
        node = stack.pop()
        flags = (node.left is not None) | (node.right is not None) << 1
        out += struct.pack("<Bi", flags, node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return bytes(out)


def decode_compact(data):
    if not data:
        return None
    pos = 0

    def go():
        nonlocal pos
        flags, val = struct.unpack_from("<Bi", data, pos)
        pos += 5
        node = Node(val)
        if flags & 1:
            node.left = go()
        if flags & 2:
            node.right = go()
        return node

    return go()

The same five-node tree:

03 01 00 00 00 00 02 00 00 00 03 03 00 00 00 00 04 00 00 00 00 05 00 00 00 25 bytes

Read as five records: 03 01000000 is node 1 with both children, 00 02000000 is leaf 2, and so on. Exactly $5n$ bytes. Two refinements are common in practice: pack the structure separately as 2 bits per node (or the succinct $2n + 1$ bit “balanced parentheses” form, which is close to the information-theoretic minimum of about $2n$ bits for the shape), and write values as variable-length integers so small numbers take one byte. Whatever the format, a decoder that reads from an untrusted source must check bounds: a truncated buffer here raises struct.error, and a decoder that trusts a length field can be made to allocate arbitrary memory.

All three round trips were checked on 3,000 random trees, including the empty tree.

Tree hashing and isomorphism

Two rooted trees are isomorphic if one can be turned into the other by reordering children. For general graphs, isomorphism has no known polynomial algorithm. For trees it is linear-time, by an algorithm Aho, Hopcroft and Ullman described in their 1974 textbook, usually called the AHU algorithm.

Canonical forms

Give every subtree a canonical name that does not depend on child order: a leaf is (), and an internal node is ( + the sorted concatenation of its children’s names + ). Two rooted trees are isomorphic exactly when their roots have the same name, because sorting removes the only freedom isomorphism allows.

def ahu_canonical(children, root):
    """Canonical string of an unordered rooted tree (AHU encoding)."""
    def enc(v):
        return "(" + "".join(sorted(enc(c) for c in children[v])) + ")"
    return enc(root)

tree a: 0 -> 1, 2;  1 -> 3     ((())())
tree b: 0 -> 1, 2;  2 -> 3     ((())())
star:   0 -> 1, 2, 3           (()()())

The string version can be quadratic in total length on deep trees, because each name contains its whole subtree. The standard fix replaces each name by a small integer: a dictionary maps “sorted tuple of child ids” to an id, shared between the trees being compared. Equal ids then mean isomorphic subtrees.

def ahu_ids(children, root, table):
    """Same idea with integer ids: equal ids <=> isomorphic subtrees.
    `table` maps a sorted tuple of child ids to an id and is shared between trees."""
    order, stack = [], [root]
    while stack:
        v = stack.pop()
        order.append(v)
        stack.extend(children[v])
    ident = {}
    for v in reversed(order):           # children before parents
        key = tuple(sorted(ident[c] for c in children[v]))
        ident[v] = table.setdefault(key, len(table))
    return ident[root]

With the sorting this is $O(n \log n)$; AHU’s original achieves $O(n)$ by processing level by level with bucket sorts. Unlike a hash function, the dictionary assigns ids with no collisions. Polynomial or random-weight hashing of trees is faster to write and works across machines, but has a small collision probability.

Unrooted trees

For unrooted trees, root each at its center: the middle vertex (or one of the middle two) of a longest path. A tree has one or two centers, found by repeatedly stripping all leaves until one or two vertices remain. Two unrooted trees are isomorphic exactly when the first tree rooted at its center matches the second rooted at one of its centers. Both the rooted and unrooted versions were checked against brute force over all vertex permutations, for random trees up to seven vertices.

Find Duplicate Subtrees

For ordered binary trees (children not interchangeable) the same id scheme gives each subtree a unique id from (value, left id, right id) without sorting, which solves Find Duplicate Subtrees (LeetCode 652) in $O(n)$ expected time:

def find_duplicate_subtrees(root):
    """One representative root per shape+values that occurs more than once."""
    ids, count, out = {}, defaultdict(int), []

    def go(node):
        if node is None:
            return 0                       # id 0 is reserved for the empty tree
        key = (node.val, go(node.left), go(node.right))
        uid = ids.setdefault(key, len(ids) + 1)
        count[uid] += 1
        if count[uid] == 2:
            out.append(node)
        return uid

    go(root)
    return out

The common alternative serializes every subtree to a string and counts the strings; it is correct but $O(n^2)$ in the worst case, since the strings for a chain have lengths $1, 2, \ldots, n$.

Flattening a tree to a linked list

Flatten Binary Tree to Linked List (LeetCode 114) rearranges the tree in place so that each node’s right pointer goes to the next node in preorder and every left pointer is None. The $O(1)$-space solution uses the same observation as Morris: in preorder, the node after the left subtree’s last node is the current node’s right child. So at each node with a left subtree, find the rightmost node of that left subtree, attach the current right subtree there, move the left subtree to the right, and continue down the right.

def flatten(root):
    """Flatten in place into a right-linked list in preorder. O(1) extra space."""
    cur = root
    while cur:
        if cur.left:
            tail = cur.left
            while tail.right:
                tail = tail.right
            tail.right = cur.right       # splice right subtree after left's tail
            cur.right = cur.left
            cur.left = None
        cur = cur.right

Time is $O(n)$ by the same right-spine argument as Morris. The recursive alternative (flatten right, flatten left, splice) is shorter to reason about but uses $O(h)$ stack. Converting a BST to a sorted doubly linked list is the inorder version of the same technique.

N-ary trees

When a node can have any number of children, store them as a list. All of the binary patterns carry over by replacing “left and right” with “for each child”.

class NNode:
    __slots__ = ("val", "children")

    def __init__(self, val, children=None):
        self.val = val
        self.children = children or []


def nary_preorder(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        stack.extend(reversed(node.children))
    return out

Some points that differ from binary trees:

• Inorder is not defined for N-ary trees; preorder, postorder and level order are. Iterative postorder is short here: run a “node, then children right to left” preorder and reverse the output.
• Height is $1 + \max$ over children, with max(..., default=0) for leaves.
• Diameter keeps the two largest child heights at each node instead of left and right.
• Serialization needs to record how many children each node has. Writing the child count after each value in preorder is enough: [1, 3, 3, 2, 5, 0, 6, 0, 2, 0, 4, 0] reads as node 1 with three children, the first being 3 with two children, and so on. The other common format is level order with a separator token after each node’s child list.
• An N-ary tree can always be converted to a binary tree with the left-child, right-sibling representation, which is a bijection; this is the usual answer to “Encode N-ary Tree to Binary Tree”.

Binary search trees

A binary search tree (BST) is a binary tree with an ordering invariant: for every node, every key in its left subtree is smaller and every key in its right subtree is larger. Equivalently, an inorder traversal produces the keys in sorted order. Every operation is a walk from the root guided by comparisons, so every operation costs $O(h)$, and the whole question with BSTs is how large $h$ gets.

Duplicates need a policy. The code here rejects them. Alternatives are to store a count in each node, or to send equal keys consistently to one side (<= goes left), which makes the invariant “left ≤ node < right” and must be applied the same way in search, insert and validate.

Search and insert

def bst_search(root, key):
    node = root
    while node and node.val != key:
        node = node.left if key < node.val else node.right
    return node


def bst_insert(root, key):
    """Iterative so a degenerate tree does not overflow the call stack."""
    new = Node(key)
    if root is None:
        return new
    node = root
    while True:
        if key < node.val:
            if node.left is None:
                node.left = new
                return root
            node = node.left
        elif key > node.val:
            if node.right is None:
                node.right = new
                return root
            node = node.right
        else:
            return root                 # no duplicates

A new key always becomes a leaf, at the place where the unsuccessful search for it ended.

Delete: three cases

Deleting key $k$ (Delete Node in a BST, LeetCode 450):

1. The node is a leaf. Remove it: the parent’s pointer becomes None.
2. The node has one child. Replace the node with that child. The child’s whole subtree lies on the same side of the parent as the deleted node did, so the invariant holds.
3. The node has two children. It cannot simply be removed, because the parent has one pointer and there would be two subtrees to hang. Instead, find its inorder successor: the smallest key in the right subtree, found by going right once and then left as far as possible. The successor is larger than everything in the left subtree and smaller than everything else in the right subtree, so it can take the deleted key’s place. Copy the successor’s key into the node, then delete the successor from the right subtree. The successor has no left child (it is the leftmost), so that second delete is case 1 or 2.

delete 5 (two children):

        5                   6                  6
      /   \               /   \              /   \
     3     8     copy    3     8    delete  3     8
          / \   ---->         / \   ---->        / \
         6   9               6   9              7   9
          \                   \
           7                   7

def bst_delete(root, key):
    if root is None:
        return None
    if key < root.val:
        root.left = bst_delete(root.left, key)
    elif key > root.val:
        root.right = bst_delete(root.right, key)
    else:
        if root.left is None:           # cases 1 and 2: zero or one child
            return root.right
        if root.right is None:
            return root.left
        succ = root.right               # case 3: two children
        while succ.left:
            succ = succ.left
        root.val = succ.val             # copy successor, delete it below
        root.right = bst_delete(root.right, succ.val)
    return root

Using the inorder predecessor (largest key in the left subtree) works equally well. Always using the successor is known to make random BSTs slowly less balanced under long sequences of random insertions and deletions (Eppinger observed this experimentally in 1983), which is one more reason production code uses a balanced tree. If nodes carry other data or other code holds references to them, copying the key is wrong; the successor node itself must be relinked into the deleted node’s place.

Validation

Validate Binary Search Tree (LeetCode 98). The classic wrong answer checks only that each node is greater than its left child and smaller than its right child. That passes this tree, which is not a BST because 3 is in the right subtree of 5:

        5
       / \
      1   6
         / \
        3   7

The invariant is about whole subtrees, so each node must lie within an open interval inherited from all its ancestors: going left tightens the upper bound, going right tightens the lower bound.

def is_valid_bst(root):
    stack = [(root, float("-inf"), float("inf"))]
    while stack:
        node, lo, hi = stack.pop()
        if node is None:
            continue
        if not lo < node.val < hi:
            return False
        stack.append((node.left, lo, node.val))
        stack.append((node.right, node.val, hi))
    return True

An equivalent check is that an inorder traversal is strictly increasing. Strict comparison rejects duplicates; adjust if the tree’s policy allows them on one side. Using infinite floats as the initial bounds is fine for numbers; for other key types, use None to mean “no bound”.

Kth smallest

Kth Smallest Element in a BST (LeetCode 230): run the iterative inorder traversal and stop at the $k$th visit. This costs $O(h + k)$ and needs no extra state.

def kth_smallest(root, k):
    stack, node = [], root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right
    return None

The kth largest is the mirror image (reverse inorder: right, node, left). If the tree is modified and queried often, store the size of each subtree in its node (an order-statistic tree). Then the search compares $k$ with the left subtree’s size and goes left, stops, or goes right with $k$ reduced, in $O(h)$ regardless of $k$. Sizes must be maintained on every insert, delete and rotation.

Inorder successor and predecessor

The successor of a key is the smallest key strictly greater than it (Inorder Successor in BST, LeetCode 285). With parent pointers there are two cases: if the node has a right subtree, it is the leftmost node there; otherwise it is the first ancestor reached by going up from a left child. Without parent pointers, a single search from the root covers both: every time the search goes left, the current node is a candidate, and the last candidate is the answer.

def successor(root, key):
    """Smallest value > key, or None. Works whether or not key is in the tree."""
    best, node = None, root
    while node:
        if node.val > key:
            best = node.val
            node = node.left
        else:
            node = node.right
    return best

The predecessor is the mirror. Both are $O(h)$ and also work for keys not in the tree, which makes them the “ceiling” and “floor” queries of an ordered map.

Building a balanced BST from sorted data

From a sorted array (Convert Sorted Array to Binary Search Tree, LeetCode 108): the middle element becomes the root, and the two halves are built recursively. Every subtree is as balanced as possible, so the height is $\lfloor \log_2 n \rfloor$, which the tests confirmed for every size.

def sorted_array_to_bst(a, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    if lo >= hi:
        return None
    mid = (lo + hi) // 2
    return Node(a[mid], sorted_array_to_bst(a, lo, mid),
                sorted_array_to_bst(a, mid + 1, hi))

$O(n)$ time. Slicing (a[:mid]) instead of passing indices makes it $O(n \log n)$ because every level copies $n$ elements.

From a sorted linked list (LeetCode 109): finding the middle of a list costs $O(n)$, which leads to $O(n \log n)$ overall. The linear method builds the tree in inorder: build the left subtree from the first $\lfloor n/2 \rfloor$ list nodes, which advances a shared list pointer past them; the next list node is the root; then build the right subtree from what remains. The list is consumed exactly once, in order.

def sorted_list_to_bst(head):
    """O(n): build the tree in inorder, consuming the list as we go."""
    n, p = 0, head
    while p:
        n += 1
        p = p.next
    cur = head

    def build_range(size):
        nonlocal cur
        if size == 0:
            return None
        left = build_range(size // 2)
        node = Node(cur.val)
        cur = cur.next
        node.left = left
        node.right = build_range(size - size // 2 - 1)
        return node

    return build_range(n)

The degenerate case

A BST built by inserting keys has a shape that depends entirely on the insertion order. Inserting sorted keys sends every key to the right of the previous one, and the tree becomes a linked list. Inserting keys in random order gives a tree whose expected height is $O(\log n)$: Devroye (1986) showed the height of a random BST is about $4.311 \ln n$ asymptotically, and the average depth of a node is about $2 \ln n \approx 1.39 \log_2 n$.

Measured heights (in edges), random order averaged over five shuffles:

At 10,000 keys the sorted build took 150 times longer than the random one, because insertion $i$ walks $i$ nodes and the total is $n^2/2$. The 100,000 sorted case was not run; extrapolating quadratically it would take well over a minute. The random heights sit around twice $\log_2 n$ and below the $4.311 \ln n$ asymptote (49.6 at 100,000), which the height approaches only slowly because of a $-1.95 \ln \ln n$ correction term.

Real data is very often sorted or nearly sorted: auto-incrementing IDs, timestamps, alphabetical imports. That is why a plain BST is almost never the right choice for a long-lived ordered map. Shuffling the input fixes the one-shot build case; for anything dynamic, use a balanced tree.

AVL trees

The AVL tree, published by Adelson-Velsky and Landis in 1962, was the first self-balancing BST. Its invariant: at every node, the heights of the left and right subtrees differ by at most 1. The balance factor of a node is $\text{height(left)} - \text{height(right)}$, and it must be −1, 0 or +1.

Why the height is logarithmic

Let $N(h)$ be the fewest nodes an AVL tree of height $h$ can have. Such a tree has a root, one subtree of height $h - 1$, and (to be as small as possible) the other of height $h - 2$:

$N(h) = N(h-1) + N(h-2) + 1, \qquad N(0) = 1,\; N(1) = 2$

This is the Fibonacci recurrence shifted by one: $N(h) = F_{h+3} - 1$. Fibonacci numbers grow like $\varphi^h$ with $\varphi \approx 1.618$, so $n \ge N(h)$ gives

$h < \log_\varphi n \approx 1.4405 \log_2 (n + 2) - 1.3277$

(in edges; in nodes, the constant is −0.3277). An AVL tree is at most about 44% taller than a perfect tree. The minimal trees, called Fibonacci trees, reach the bound:

Rotations

When an insertion makes some node’s balance factor ±2, a rotation fixes it. A rotation changes the shape of three nodes while preserving the inorder sequence, so the BST invariant survives.

right rotation at y                 left rotation at x

        y                x                  x                  y
       / \              / \                / \                / \
      x   C    --->    A   y              A   y    --->      x   C
     / \                  / \                / \            / \
    A   B                B   C              B   C          A   B

In both, A < x < B < y < C before and after. Only two pointers change, and only the heights of x and y need recomputing.

There are four imbalance cases, named by the path from the unbalanced node to the inserted key:

The double rotations exist because a single rotation in the Left-Right case moves the heavy middle subtree (B in the diagram) from one side to the other without reducing the height.

Implementation

class AVLNode:
    __slots__ = ("key", "left", "right", "h")

    def __init__(self, key):
        self.key = key
        self.left = self.right = None
        self.h = 1                       # height in nodes; empty = 0


def _h(n):
    return n.h if n else 0


def _fix(n):
    n.h = 1 + max(_h(n.left), _h(n.right))


def _rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    _fix(y)
    _fix(x)
    return x


def _rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    _fix(x)
    _fix(y)
    return y


def _rebalance(n):
    _fix(n)
    bf = _h(n.left) - _h(n.right)
    if bf > 1:
        if _h(n.left.left) < _h(n.left.right):   # left-right case
            n.left = _rotate_left(n.left)
        return _rotate_right(n)                  # left-left case
    if bf < -1:
        if _h(n.right.right) < _h(n.right.left): # right-left case
            n.right = _rotate_right(n.right)
        return _rotate_left(n)                   # right-right case
    return n


def avl_insert(n, key):
    if n is None:
        return AVLNode(key)
    if key < n.key:
        n.left = avl_insert(n.left, key)
    elif key > n.key:
        n.right = avl_insert(n.right, key)
    else:
        return n
    return _rebalance(n)

The order inside _rotate_right matters: y is now below x, so y’s height must be fixed first. The recursion depth is the tree’s height, which the invariant keeps logarithmic. After an insertion at most one rotation (single or double) is needed, because it restores the subtree’s height to what it was before the insertion. Deletion uses the same _rebalance on the way back up, but may need a rotation at every level, $O(\log n)$ of them.

The implementation was checked after every single insertion on 300 random sequences with a function that verifies the balance factors, stored heights and BST ordering of every node.

Measured height

Sorted input, the plain BST’s worst case, is the AVL tree’s best: the rotations produce a nearly perfect tree with height $\lfloor \log_2 n \rfloor$. Random input gives trees about 15% taller than perfect, well under the 44% bound, which only adversarial sequences reach. Compare the plain BST: 99,999 for sorted input at $n = 100{,}000$, against 16 here.

Red-black trees

A red-black tree colors each node red or black and enforces five invariants (in the form given by Cormen, Leiserson, Rivest and Stein):

1. Every node is red or black.
2. The root is black.
3. Every leaf (the NIL sentinel standing for an empty child) is black.
4. A red node has two black children. Equivalently, there are no two reds in a row on any path.
5. For each node, every path from it down to a NIL leaf contains the same number of black nodes. This number is the node’s black-height.

The structure was introduced by Guibas and Sedgewick in 1978, as a binary encoding of Bayer’s 1972 “symmetric binary B-trees”. The correspondence is useful: a black node together with its red children forms one node of a 2-3-4 tree (a B-tree of order 4), so a red-black tree is a 2-3-4 tree written with binary nodes.

Why the height is at most $2 \log_2(n+1)$

Two facts combine.

1. A subtree rooted at $x$ contains at least $2^{\text{bh}(x)} - 1$ internal nodes. By induction: a leaf has black-height 0 and contains $2^0 - 1 = 0$ internal nodes; each child of $x$ has black-height at least $\text{bh}(x) - 1$, so $x$‘s subtree has at least $2\,(2^{\text{bh}(x)-1} - 1) + 1 = 2^{\text{bh}(x)} - 1$ nodes.
2. By invariant 4, at least half the nodes on any root-to-leaf path are black, so $\text{bh}(\text{root}) \ge h/2$.

Together: $n \ge 2^{h/2} - 1$, so $h \le 2 \log_2(n + 1)$. Intuitively, invariant 5 makes the all-black skeleton perfectly balanced, and invariant 4 lets the longest path be at most twice the shortest, by interleaving a red node after every black one.

Red-black versus AVL

The red-black bound (factor 2) is looser than AVL’s (factor 1.44), so AVL trees are somewhat shorter and lookups slightly faster. The red-black advantage is in updates: an insertion needs at most two rotations and a deletion at most three, plus $O(\log n)$ recoloring in the worst case and $O(1)$ amortized. AVL deletion can need a rotation at every level. Rotations matter more than recoloring when nodes carry augmented data (subtree sizes, interval maximums) that has to be recomputed on every structural change, or in persistent and concurrent variants where each structural change is expensive.

Where they are used

• Linux kernel. lib/rbtree.c provides intrusive red-black trees used throughout the kernel. The CFS scheduler kept runnable tasks in an rbtree ordered by virtual runtime and always picked the leftmost. The EEVDF scheduler that replaced it in Linux 6.6 still uses an augmented rbtree, with each node caching a value from its subtree so that the eligible task with the earliest deadline can be found in $O(\log n)$. Other users include epoll’s set of watched file descriptors and many file-system and timer structures. (Memory-area lookup used an rbtree until Linux 6.1, when it moved to the maple tree, a B-tree variant.)
• Java. java.util.TreeMap and TreeSet are documented as red-black trees, with guaranteed $O(\log n)$ get, put and remove. Since Java 8, HashMap also converts a bucket with many colliding keys into a small red-black tree.
• C++. The standard specifies std::map and std::set only by complexity and iterator guarantees, not by data structure. A frequent claim is that the standard requires red-black trees; it does not. In practice all three major implementations (libstdc++, libc++ and Microsoft’s STL) use red-black trees.

Implementing red-black deletion correctly takes about a page of careful case analysis and is a common source of bugs; this chapter does not reproduce it. Sedgewick’s left-leaning red-black tree (2008) reduces the code considerably by forcing red links to lean left, at some cost in constant factors.

B-trees and B+ trees

Every balanced binary tree has height about $\log_2 n$: 20 levels for a million keys, 30 for a billion. In memory that is fine. On a disk it is not, because each level is a separate random read, and a random read from storage costs on the order of 10 milliseconds on a spinning disk and around 100 microseconds on an SSD, against roughly 100 nanoseconds for a main-memory access. Storage is also read in fixed-size pages (PostgreSQL uses 8 KB), so reading one 32-byte binary-tree node fetches a whole page and throws most of it away.

The B-tree, introduced by Bayer and McCreight in 1972, fixes both problems by making each node a whole page holding many keys. A node with $m$ keys has $m + 1$ children, and the keys separate the children’s ranges, like a BST node generalized to many-way branching. With fan-out $b$ the height is about $\log_b n$. For $b = 500$ that is three levels for 100 million keys, and the top level or two is almost always in memory, so a lookup costs one or two page reads.

Invariants

Using the minimum degree $t \ge 2$ convention of Cormen and colleagues:

1. Every node except the root holds between $t - 1$ and $2t - 1$ keys, kept sorted. The root holds between 1 and $2t - 1$ (or 0 if the tree is empty).
2. An internal node with $k$ keys has exactly $k + 1$ children, and the keys separate the key ranges of those children.
3. All leaves are at the same depth.

Invariant 3 is what makes a B-tree balanced, and it is maintained by the unusual way B-trees grow: upward, at the root, never downward at a leaf.

(The literature also uses “order” for the maximum number of children, as in Knuth. Order 4 in that convention is $t = 2$ here, the 2-3-4 tree.)

Insertion by splitting

A new key always goes into a leaf. If the leaf is full ($2t - 1$ keys), it is split: its median key moves up into the parent, and the keys on either side become two nodes of $t - 1$ keys each. The parent might then be full and need splitting too. When the root splits, a new root is created above it with one key, and that is the only way the height ever increases, by one level for the whole tree at once.

The variant below splits full nodes preemptively on the way down, so the parent always has room for the median and the insertion is a single downward pass.

t = 2 (at most 3 keys per node); insert 1..7 in order

insert 1,2,3:   [1 2 3]

insert 4: root full, split around 2 first:
                  [2]
                 /   \
              [1]    [3 4]

insert 5,6: leaf [3 4 5] fills; inserting 6 splits it around 4:
                 [2 4]
                /  |  \
             [1]  [3]  [5 6]

insert 7:        [2 4]
                /  |  \
             [1]  [3]  [5 6 7]

class BTreeNode:
    __slots__ = ("keys", "children")

    def __init__(self):
        self.keys = []
        self.children = []               # empty for a leaf


class BTree:
    """CLRS-style B-tree of minimum degree t: every node except the root has
    t-1 .. 2t-1 keys. Insertion splits full nodes on the way down."""

    def __init__(self, t):
        self.t = t
        self.root = BTreeNode()

    def search(self, key):
        from bisect import bisect_left
        node = self.root
        while True:
            i = bisect_left(node.keys, key)
            if i < len(node.keys) and node.keys[i] == key:
                return True
            if not node.children:
                return False
            node = node.children[i]

    def _split_child(self, parent, i):
        t = self.t
        full = parent.children[i]
        right = BTreeNode()
        middle = full.keys[t - 1]
        right.keys = full.keys[t:]
        full.keys = full.keys[:t - 1]
        if full.children:
            right.children = full.children[t:]
            full.children = full.children[:t]
        parent.keys.insert(i, middle)
        parent.children.insert(i + 1, right)

    def insert(self, key):
        from bisect import bisect_left
        root = self.root
        if len(root.keys) == 2 * self.t - 1:   # grow upward: the only way height increases
            new_root = BTreeNode()
            new_root.children.append(root)
            self._split_child(new_root, 0)
            self.root = new_root
        node = self.root
        while node.children:
            i = bisect_left(node.keys, key)
            if i < len(node.keys) and node.keys[i] == key:
                return
            if len(node.children[i].keys) == 2 * self.t - 1:
                self._split_child(node, i)
                if key > node.keys[i]:
                    i += 1
                elif key == node.keys[i]:
                    return
            node = node.children[i]
        i = bisect_left(node.keys, key)
        if i < len(node.keys) and node.keys[i] == key:
            return
        node.keys.insert(i, key)

Searching inside a node uses binary search (bisect), so a lookup costs $O(\log_b n)$ node visits and $O(\log_2 b)$ comparisons per node, $O(\log_2 n)$ comparisons in total: the same comparison count as a binary tree, with far fewer page reads. The implementation was checked for ordering, occupancy and equal leaf depth on 300 random insertion sequences with $t$ = 2, 3 and 5.

Deletion is the mirror image and more intricate. Before descending into a child that has only the minimum $t - 1$ keys, the algorithm tops it up by borrowing a key through the parent from a sibling, or by merging it with a sibling and pulling a separator key down. If the root ends up with no keys, its single child becomes the root, and the tree shrinks by one level. Real databases often relax this and allow underfull pages, reclaiming space later, because merging under concurrent access is expensive.

Measured height

One million random keys:

With up to 511 keys per node, every one of a million keys is at most two links below the root: three node reads in total, against around 20 for a balanced binary tree.

B+ trees

Almost every database and file system actually uses a B+ tree, which changes two things:

• All values (or row pointers) live in the leaves. Internal nodes hold only separator keys used for routing. Without values, more keys fit in each internal page, so the fan-out is higher and the tree shorter.
• Leaves are linked into a list in key order. A range scan (WHERE created_at BETWEEN ..., ORDER BY ... LIMIT) finds the first key with one descent and then walks sideways along the leaves, without going back up the tree.

                  [ 30 | 60 ]                    internal: keys only
               /       |       \
    [10 20] <-> [30 40 50] <-> [60 70]           leaves: keys + values, linked

A separator key in an internal node may be a copy of a leaf key, or even a shortened prefix that merely separates the two sides (“suffix truncation”), which lets even more fit per page.

PostgreSQL’s default index type is a B+ tree in this sense, based on the Lehman and Yao design that adds a right-link to each page so that readers do not need to lock the path from the root while pages split concurrently. Its index pages, how a lookup turns into heap reads, and when the planner chooses a B-tree are covered in PostgreSQL indexes.

Skip lists

A skip list, published by William Pugh in 1990, provides the same ordered-map operations as a balanced tree with a different idea: a sorted linked list where each node also appears, with probability 1/2 (or 1/4), in an express list above it, and so on upward. A search starts in the sparsest list and drops down a level whenever the next step would overshoot.

The skip list’s practical strengths are local updates (an insert changes only the predecessors at each of the new node’s levels) and the ease of building concurrent versions. Redis uses one for sorted sets, combined with a hash table for member lookup; see Redis internals.

Summary