Trees & Tries

The 30-second version

You already use trees every day, even if nobody called them that:

• Folders on your laptop. /home/alice/notes.txt: a folder contains folders and files, which contain more.
• A web page. The browser turns your HTML into the DOMDOMThe Document Object Model: the browser's tree of objects that represents the page. Every button, input and div is a DOM node you can attach event listeners to., a tree of elements: <body> holds <nav> and <main>, which hold links and paragraphs.
• JSONJSONJavaScript Object Notation: a text format for data — {"id": 7, "tags": ["a"]}. Readable by humans and every language; the default body format for web APIs.. Objects inside objects inside arrays.
• An org chart or a family tree. One person at the top, branching down.
• Your code. Before a compiler, linter or bundler does anything with total = price * qty + tax, it turns it into a tree called an ASTAST (abstract syntax tree)The tree a compiler, linter or bundler builds from source code: a + b * c becomes a + node whose right child is a * node. Prettier, ESLint, Babel and go/ast all work on ASTs..

Why a whole topic on trees?

Because one shape does three very different jobs:

The catch in job 2 is the most important idea in this topic: a tree is only fast if it is short. Feed a naive sorted tree already-sorted data and it degrades into a long chain, as slow as scanning a list. Balancing tricks (§07) exist to stop that from happening.

Root, leaf, depth, height

Here are the words you'll meet in every tree discussion. Each one is shown in the widget below, so click around while you read.

• A nodeNode (in a tree)One box in the tree: it holds a value plus links (pointers) to its children. A folder, an HTML element or one entry of a BST is a node. is one box: some data plus links to its children.
• The rootRoot, parent, child, leafThe root is the single node at the top, with no parent. A node's children hang directly below it; it is their parent. A leaf is a node with no children. is the one node with no parent. A node's children hang directly below it, and it is their parent. A leaf has no children.
• The depthDepth and heightDepth of a node = how many links you follow from the root to reach it (the root has depth 0). Height of a tree = how many levels it has, i.e. the longest root-to-leaf path counted in nodes. A lookup visits at most height nodes. of a node is how many links you follow from the root to reach it. The root has depth 0.
• The height of a tree is how many levels it has. A tree that's just a root has height 1. A lookup that walks from the root downward visits at most height nodes, which is why height decides speed.
• A subtreeSubtreeA node together with everything below it. Every child of a node is the root of its own smaller tree — which is why tree code is usually recursive. is any node plus everything below it. Every child is the root of its own smaller tree.

The one idea that makes tree code short

Look at the widget again: pick any node, and its subtree is a complete tree in its own right. So a question about a whole tree (“how many files?”, “what's the total size?”) can be answered by asking the same question of each child's subtree and combining the answers.

A function that solves a problem by calling itself on smaller pieces is called RecursionRecursionA function that solves a problem by calling itself on smaller pieces of it — e.g. a folder's size is the sum of its children's sizes, and a child folder computes its size the same way. It stops at pieces with no children.. Nearly every tree algorithm in this topic is three lines of recursion. The Composite pattern is this same idea dressed up as a design pattern: a folder answers Size() by summing its children's Size().

What a node looks like in code

A general tree node holds a value and a list of children. A binary tree is the special case where every node has at most two children, called Left and Right; that's the shape behind the search trees in §04.

// Any number of children (a folder, a DOM element)
type Dir struct {
    Name     string
    Children []*Dir // a slice of pointers to other nodes
}

// At most two children (a binary tree)
type Node struct {
    Val         int
    Left, Right *Node // nil = "no child here"
}

// Height in levels: recursion in three lines
func height(n *Node) int {
    if n == nil {
        return 0 // an empty tree has no levels
    }
    return 1 + max(height(n.Left), height(n.Right))
}

Notice how height works: an empty tree has 0 levels; any other tree has its own level plus the taller of its two subtrees. You'll see this shape (“handle nil, then recurse left and right”) in almost every snippet that follows.

Walking a tree: four orders

Depth-first traversals (DFSDFS (depth-first search)Exploring a graph by following one path as far as it goes, then backing up to the latest fork and trying the next branch. Uses recursion or a stack.) all follow the same recipe at every node: handle the left subtree, handle the right subtree, and handle this node somewhere in between. Where you put “this node” gives the three names:

Step through all four on the same tree. Watch the right-hand panel: depth-first orders keep a stack of unfinished calls, level-order keeps a queue.

The code: three functions that differ by one line

func preorder(n *Node, visit func(int)) {
    if n == nil {
        return // empty subtree: nothing to do
    }
    visit(n.Val) // ← pre: me first…
    preorder(n.Left, visit)
    preorder(n.Right, visit)
}

func inorder(n *Node, visit func(int)) {
    if n == nil {
        return
    }
    inorder(n.Left, visit)
    visit(n.Val) // ← in: …between my children…
    inorder(n.Right, visit)
}

func postorder(n *Node, visit func(int)) {
    if n == nil {
        return
    }
    postorder(n.Left, visit)
    postorder(n.Right, visit)
    visit(n.Val) // ← post: …or after them
}

Where's the stack? Doing it by hand

Recursion hides a stackStack (data structure)A last-in, first-out pile: you push onto the top and pop from the top, like a stack of plates. (The call stack is one.): each call that hasn't finished yet waits on the program's call stack. You can do the same job with your own stack (a slice or array you push to and pop from), and level-order is the same loop with a queueQueue (data structure)A first-in, first-out line: you add at the back and remove from the front, like people waiting at a checkout. instead:

// Same output as preorder, with our own stack instead of the call stack.
func preorderLoop(root *Node) []int {
    var out []int
    stack := []*Node{root}
    for len(stack) > 0 {
        n := stack[len(stack)-1]     // look at the top…
        stack = stack[:len(stack)-1] // …and pop it
        if n == nil {
            continue
        }
        out = append(out, n.Val)
        stack = append(stack, n.Right, n.Left) // push Right first so Left pops first
    }
    return out
}

// Breadth-first: a queue instead of a stack.
func levelOrder(root *Node) []int {
    var out []int
    queue := []*Node{root}
    for len(queue) > 0 {
        n := queue[0]     // take from the front…
        queue = queue[1:] // …and drop it
        if n == nil {
            continue
        }
        out = append(out, n.Val)
        queue = append(queue, n.Left, n.Right) // children wait at the back
    }
    return out
}

loop:  [8 3 1 6 4 7 10 14 13]
level: [8 3 10 1 6 14 4 7 13]

Recursive or loop?

Write the recursive version first: it's shorter and obviously right. Switch to an explicit stack when the tree can be very deep. Each recursive call uses some call-stack memory, and in JavaScript that runs out: on Node 22 with default settings, our recursive inorder crashes with RangeError: Maximum call stack size exceeded after roughly 10,000 nested calls (a Stack overflowStack overflowThe crash you get when the call stack runs out of room — usually because a recursive function never stops calling itself, or recurses too deeply (tens of thousands of levels in JS). JS throws “RangeError: Maximum call stack size exceeded”; Go prints “fatal error: stack overflow”.). Nothing is wrong with the code — the recursion does end — it's just deeper than the stack allows. Go grows goroutine stacks automatically (up to 1 GB by default), so it survives far deeper trees, but it still spends memory per level.

How does a tree get 10,000 levels deep? §06 shows how ordinary sorted data does it to a search tree.

Binary search trees: higher or lower?

The rule

For every node — not just the root — all keys in its left subtree are smaller and all keys in its right subtree are bigger. This is the BST invariantBST invariantThe rule a binary search tree must never break: for every node, all keys in its left subtree are smaller and all keys in its right subtree are bigger. Every operation must leave this true.: every operation must leave it true, and every operation relies on it being true.

Search: walk down, one comparison per level

Start at the root. If the key you want is smaller, go left; bigger, go right; equal, you found it. If you fall off the bottom (reach nil), the key isn't there. You never look at the other side of any node, because the rule promises the key can't be there.

Insert: search, then fill the empty spot

Do the same walk. When you fall off the bottom, the empty spot you fell into is exactly where the new key belongs. Hang a new node there. Nothing else moves.

Try both. Search for 65, insert 45 and 33, and watch the comparison counter:

Why it's fast: cost = height

Each comparison moves you down one level, so the number of comparisons is at most the tree's height. How small can the height be? A tree where every level is full holds 1 + 2 + 4 + … keys:

Each extra level doubles the capacity. Turn that around: n keys need only about log₂ n levels. “log₂ n” just means how many times you can halve n before you reach 1: for a million, about 20. That's what “O(log n)” means here (see Big-O for the notation): a million keys, at most ~20 comparisons, if the tree is well shaped.

That “if” is the whole story of §06 and §07. Press “insert 1…7 in order” in the playground and look at the shape you get.

Free bonus: sorted order

Walk any BST in-order — visit the left subtree, then the node, then the right subtree, at every node (§03 animates it) — and the keys come out sorted. Why: in-order prints the left subtree (all smaller), then the node, then the right subtree (all bigger), and the same holds inside every subtree.

This is what a BST gives you that a Hash mapHash mapA key → value table (Go's map, JS's Map) that turns each key into a number with a hash function and uses it to jump straight to a slot. Lookups take about the same time however big it gets. can't. A hash map finds exact keys faster, but it keeps them in no particular order. A BST can also answer:

• “What's the smallest key?” (go left until you can't)
• “What's the next key after 42?”
• “Give me every key between 100 and 200, in order.” (a Range queryRange queryA query asking for all values between two bounds — created_at between March 1 and March 2, price < 100 — instead of one exact value.)

A map that keeps its keys in order like this is called a sorted mapSorted (ordered) mapA key → value map that also keeps keys in order, so you can ask for the smallest key, the next key after x, or every key between a and b. Java's TreeMap and C++'s std::map are sorted maps; Go's map and JS's Map are not.. That's the main reason to use a tree over a hash map.

Deleting: the three cases

Insert never moves existing nodes; delete sometimes has to. The difficulty is that a node's parent has one pointer to it, and that pointer has to keep pointing at something that obeys the BST rule.

Why the successor always works

The in-order successorIn-order successorThe next bigger key in the tree. For a node with a right child, it's the leftmost (smallest) node of its right subtree: one step right, then left as far as possible. of a node is the next bigger key in the whole tree. When the node has a right child, the successor is in its right subtree, at the far left: one step right, then left until you can't.

That key is the perfect stand-in, for two reasons:

1. It's bigger than every key in the left subtree (it came from the right side), so the left side is still fine.
2. It's smaller than every other key in the right subtree (it was the smallest there), so the right side is still fine.

And removing it from its old spot is always easy: it was the leftmost node, so it has no left child. That makes its removal case 1 or case 2 — never case 3 again.

In code

All three cases fit in a few lines. This uses the same Node type as §02 and §03 (Val, Left, Right); in a search tree, Val is the key. The function returns the new root of each subtree, so the parent simply stores whatever comes back. That's how “the parent's pointer now points at the child” happens without any parent pointers:

// type Node struct { Val int; Left, Right *Node } — from §02

func remove(n *Node, key int) *Node {
    if n == nil {
        return nil // key wasn't there
    }
    switch {
    case key < n.Val:
        n.Left = remove(n.Left, key)
    case key > n.Val:
        n.Right = remove(n.Right, key)
    default: // n is the node to delete
        if n.Left == nil {
            return n.Right // case 1 (both nil) or case 2 (only a right child)
        }
        if n.Right == nil {
            return n.Left // case 2: only a left child
        }
        succ := n.Right // case 3: find the successor…
        for succ.Left != nil {
            succ = succ.Left
        }
        n.Val = succ.Val                    // …copy its key here (in a map, copy the value too)…
        n.Right = remove(n.Right, succ.Val) // …and delete it below (case 1 or 2)
    }
    return n
}

Run it on the §03 tree (root 8) with inorder from §03:

root = remove(root, 3) // 3 has two children: its successor 4 takes its place
inorder(root, func(v int) { fmt.Print(v, " ") })

1 4 6 7 8 10 13 14

Case 1 needs no code of its own: if both children are nil, return n.right returns nil, which is exactly “cut it off”. §09 wraps these functions into a reusable, tested type.

Why balance matters

Watch it happen

Insert 1, 2, 3, 4, 5 into an empty BST. 1 becomes the root. 2 is bigger, so it goes right. 3 is bigger than 1 and 2, so it goes right of 2. Every key goes right of the one before it:

1
 \
  2
   \
    3
     \
      4
       \
        5

That's a Linked listLinked listA list where each item (a “node”) stores a value plus a pointer to the next node. Nodes can be anywhere in memory, so walking the list jumps around. with extra steps. Searching for 5 takes 5 comparisons; with 1,000,000 keys inserted in order, it's 1,000,000 comparisons instead of ~20. In Big-O notationBig-O notationA way to describe how an algorithm's cost grows as the input grows, ignoring constant factors: O(1) stays flat, O(n) grows in step with n, O(n²) quadruples when n doubles. terms every operation slid from O(log n) to O(n). You saw the same shape in the §04 playground with “insert 1…7 in order”.

The four bars, top to bottom:

1. Sorted inserts, plain BST: height = n. The disaster case.
2. The same keys, shuffled: much better. Random insert orders give a height of a few times log₂ n on average, but it's luck, not a promise.
3. An AVL tree, fed the same sorted keys: it rearranges itself as it goes (§07) and stays close to the minimum.
4. The best possible: a perfectly full tree.

“But my data isn't sorted”

It often is, or nearly so:

• Auto-increment IDs (1, 2, 3, …) and timestamps arrive in increasing order by definition.
• Loading a file or export that was already sorted, or the result of an ORDER BY query.
• Data that's mostly sorted with a few exceptions builds long chains too.

So a plain BST is fine for learning and for data you know is random, but anything that takes outside input needs a guarantee. There are two ways to get one: make the tree fix its own shape after each change (§07), or use a different structure entirely (a sorted slice or a B-tree, §10).

Self-balancing trees: rotations, AVL, red-black

A balanced treeBalanced treeA tree kept close to its minimum possible height (about log₂ n levels for n keys), so every lookup, insert and delete stays O(log n). Without balancing, bad insert orders can make the height grow to n. stays close to the minimum height of about log₂ n. The tool every balanced BST uses is the same.

The rotation

A rotationRotationA local rearrangement of two nodes and their three subtrees that makes one node the parent of the other while keeping the sorted (in-order) order unchanged. It changes the height of the subtrees — the tool all balanced BSTs use. takes a node x and its child y and makes y the parent instead. The three subtrees hanging below them (A, B, C — each could be empty or huge) get reattached so the BST rule still holds. Step through it:

1func rotateLeft(x *Node) *Node {
2    y := x.Right
3    x.Right = y.Left // B moves
4    y.Left = x       // x under y
5    return y         // parent → y
6}

Three facts make rotations the right tool:

• Sorted order is preserved. Read the nodes left to right before and after: A, x, B, y, C. Only the shape changed.
• They change height. A left rotation moves one level of height from the right side to the left side.
• They're cheap. Three pointer assignments, whatever the size of A, B and C. Nothing is copied.

Some lopsided shapes need two rotations. If the tall part is on the right child's left side (a zig-zag shape), you first rotate the child right to straighten it, then rotate the node left. That's called a double rotation; it's still just the same move used twice. Insert 1, 3, 2:

zig-zag:            rotate right at 3:       rotate left at 1:
                    (now a straight line)

  1                   1                          2
   \                   \                        / \
    3                   2                      1   3
   /                     \
  2                       3

One rotation at 1 alone wouldn't help here: 2 would end up as 1's right child, still a zig-zag, just mirrored.

AVL trees: the strict rule

An AVL treeAVL treeThe first self-balancing BST (1962, named after Adelson-Velsky and Landis). For every node, the heights of its two subtrees differ by at most 1. Very tightly balanced: height stays under about 1.44 × log₂ n. (1962, the first self-balancing BST) stores each node's height and enforces one rule: at every node, the left and right subtree heights differ by at most 1. That difference is the node's balance factorBalance factorIn an AVL tree: height of a node's left subtree minus height of its right subtree. It must stay −1, 0 or +1; a ±2 triggers a rotation..

After an insert or delete, walk back up the path you came down, updating heights. If any node's balance factor reaches ±2, rotate there (once or twice). That's it. Insert 1, 2, 3 in order:

after inserting 1, 2, 3:              rotate left at 1:

  1   ← balance factor −2                  2
   \    (left height 0, right 2)          / \
    2                                    1   3
     \
      3

The guarantee: an AVL tree's height is at most about 1.44 × log₂ n. For a million keys, under 29 levels — in practice usually 20 or 21.

Red-black trees: the relaxed rule

A red-black treeRed-black treeA self-balancing BST that colors every node red or black and enforces a few color rules. The rules guarantee no path is more than twice as long as any other, so height ≤ 2 × log₂(n+1). Java's TreeMap and C++'s std::map use one. colors every node red or black and enforces a few rules. You don't need to memorize them to use one, but here they are:

1. The root is black, and the empty spots (nil) count as black.
2. A red node can't have a red child (no two reds in a row).
3. Every path from a node down to an empty spot passes through the same number of black nodes.

Rule 3 makes all paths equally long if you count only black nodes. Rule 2 means the red nodes can at most double a path's length: at worst a path alternates black, red, black, red…, so it has no more reds than blacks. Together: no path is more than twice as long as any other, and height ≤ 2 × log₂(n+1). For a million keys, at most ~40 levels.

Fixing a broken rule after an insert or delete takes recoloring (cheap) plus at most two rotations for an insert and three for a delete. An AVL tree also needs at most two rotations per insert, but a delete may need a rotation at every level on the way back up.

Both give the same Big-O notationBig-O notationA way to describe how an algorithm's cost grows as the input grows, ignoring constant factors: O(1) stays flat, O(n) grows in step with n, O(n²) quadruples when n doubles. guarantee: O(log n) per operation, whatever order the keys arrive in. That guarantee is what you're buying.

Simpler alternatives that balance on average

• A treapTreapA BST where each node also gets a random priority, and nodes with higher priority sit above lower ones (like a heap). The randomness keeps it balanced on average, with much simpler code than red-black trees. gives every node a random priority and keeps higher priorities above lower ones. The randomness makes the shape behave like a shuffled insert order no matter what order keys arrive in. It's much less code than red-black, and the guarantee is “O(log n) with overwhelming probability” rather than always.
• A skip listSkip listA sorted linked list with extra “express lane” links that skip over many nodes, so finding or inserting a key takes about log(n) steps — like a balanced tree, but simpler to make safe for concurrent writers. Most memtables are skip lists. isn't a tree at all: it's a sorted linked list with random “express lanes”. It's easier to make safe for concurrent writers, which is why many databases' in-memory write buffers use one (see LSM Trees).
• A B-tree solves the problem a different way: hundreds of keys per node, so the tree is short and wide (§10).

Tries: trees for prefixes

Each node also needs a flag meaning “a word ends here”. Without it, storing “card” would make it look like “car” and “ca” were words too. In the widget, a double ring marks those nodes.

Things to try:

• Type ca, then car, then cart. The walk down costs one step per letter typed, whether the trie holds 8 words or 8 million. Lookup cost depends on the length of the key, not on how many keys are stored.
• Insert cars: only one new node, because c-a-r already exists.
• Type x: the walk stops at the root immediately. “No word starts with x” is answered after one step.

Why not a hash map or a BST?

A Hash mapHash mapA key → value table (Go's map, JS's Map) that turns each key into a number with a hash function and uses it to jump straight to a slot. Lookups take about the same time however big it gets. answers only “is exactly this key stored?”. To list everything starting with “car” you'd scan every key. A BST can do prefix searches (all keys from “car” up to “cas” form one sorted range), but every comparison along the way re-reads the strings from the first letter, so the shared prefix is read again at every level. A trie reads each character of your key once.

The memory problem, and radix trees

Plain tries are wasteful. Every node is a separate allocation with its own children table, and long words with no siblings build chains of single-child nodes. Click + dolphin: that adds five new nodes in a row (l, p, h, i, n), used by exactly one word.

A radix treeRadix tree (compressed trie)A trie where chains of single-child nodes are merged into one node holding a whole string fragment (e.g. “lphin” instead of five nodes). Same answers, far fewer nodes. Used by HTTP routers and IP routing tables. (also called a compressed trie, or Patricia trie) merges every such chain into one node holding a fragment, like “lphin”. Flip the widget to radix and compare the node counts. Same words, same lookups, far fewer nodes. Real implementations almost always use the compressed form.

How each node stores its children is the other big trade-off:

Where tries run in production

HTTP routers. Routing /users/:id/posts means matching the request path against hundreds of patterns that share prefixes. Go's popular httprouter package, and frameworks built on it like Gin, store routes in a radix tree. Go's own net/http.ServeMux (Go 1.22 and later) matches patterns with a tree that branches on host, method, then one path segment per level.

IP routing. A RouterRouterA device that forwards packets between networks, choosing the next hop toward each packet's destination address. Your home Wi-Fi box is one; the internet is thousands of them.'s routing tableRouting table (IP)A router's list of rules of the form “addresses starting with these bits → send the packet out this link”, e.g. 10.1.0.0/16 → link B. When several rules match an address, the most specific one (the longest matching prefix) wins. holds rules like “10.0.0.0/8 → link A” and “10.1.0.0/16 → link B” (that's CIDR notationCIDR notation (/24)Writing a subnet as address/number, e.g. 192.168.1.0/24. The number says how many leading bits are the fixed network part; the rest are free for hosts. /24 leaves 8 bits = 256 addresses. The same thing as a “subnet mask” like 255.255.255.0. notation: the first 8 or 16 bits are fixed). A packet for 10.1.2.3 matches both, and the router must pick the most specific one. That's Longest-prefix matchLongest-prefix matchPicking the most specific rule that matches the start of a key. An IP router with routes for 10.0.0.0/8 and 10.1.0.0/16 sends 10.1.2.3 via the /16 because it matches more leading bits.. Put the rules in a trie keyed by the address's bits (a binary trie: one level per bit, two children per node), walk down following 10.1.2.3's bits, and the last rule you passed on the way is the answer. The Linux kernel's IPv4 routing table is a compressed trie of this kind.

Autocomplete, spell checkers, word games. Anything that asks “which stored strings start with this?” or “is this a prefix of any word?”.

Build it: a generic BST and a trie

This is a plain, unbalanced BST: perfect for learning and for random keys, but remember §06 before using it on real input.

The BST in Go

package main

import (
    "cmp"
    "iter"
)

// node is one box in the tree: a key and two child pointers.
type node[K cmp.Ordered] struct {
    key         K
    left, right *node[K]
}

// BST works for any key type that supports < and > (ints, floats, strings…).
type BST[K cmp.Ordered] struct {
    root *node[K]
}

func (t *BST[K]) Insert(key K) { t.root = insert(t.root, key) }
func (t *BST[K]) Delete(key K) { t.root = remove(t.root, key) } // §05's remove, made generic
func (t *BST[K]) Height() int   { return height(t.root) }        // §02's height, made generic

func insert[K cmp.Ordered](n *node[K], key K) *node[K] {
    if n == nil {
        return &node[K]{key: key} // ← the empty spot where key belongs
    }
    switch {
    case key < n.key:
        n.left = insert(n.left, key)
    case key > n.key:
        n.right = insert(n.right, key)
    } // equal: already present, nothing to do
    return n
}

// Contains walks down without recursion: left if smaller, right if bigger.
func (t *BST[K]) Contains(key K) bool {
    n := t.root
    for n != nil {
        switch {
        case key < n.key:
            n = n.left
        case key > n.key:
            n = n.right
        default:
            return true
        }
    }
    return false // fell off the bottom
}

// All yields the keys in sorted order (an in-order traversal).
func (t *BST[K]) All() iter.Seq[K] {
    return func(yield func(K) bool) { inorder(t.root, yield) }
}

func inorder[K cmp.Ordered](n *node[K], yield func(K) bool) bool {
    if n == nil {
        return true
    }
    // && stops early if any part returns false (the caller broke out of its loop)
    return inorder(n.left, yield) && yield(n.key) && inorder(n.right, yield)
}

Using it:

var t BST[int]
for _, k := range []int{8, 3, 10, 1, 6, 14, 4, 7, 13} {
    t.Insert(k)
}
fmt.Println(slices.Collect(t.All()), t.Contains(6), t.Contains(5))
t.Delete(3) // two children → replaced by its successor, 4
fmt.Println(slices.Collect(t.All()))

var words BST[string] // same code, different key type
for _, w := range []string{"pear", "apple", "fig"} {
    words.Insert(w)
}
fmt.Println(slices.Collect(words.All()))

$ go run .
[1 3 4 6 7 8 10 13 14] true false
[1 4 6 7 8 10 13 14]
[apple fig pear]

Testing it against a model

Hand-picked test cases miss the weird shapes. Instead, generate 10,000 random inserts and deletes, apply each one to the tree and to a sorted slice (too slow for real use, but obviously correct), and check that they always agree:

func TestBSTMatchesSortedSlice(t *testing.T) {
    r := rand.New(rand.NewPCG(1, 2)) // fixed seed → the same run every time
    var tree BST[int]
    var want []int // the "obviously correct" model
    for range 10_000 {
        k := r.IntN(500)
        if r.IntN(3) == 0 { // one operation in three is a delete
            tree.Delete(k)
            if i, found := slices.BinarySearch(want, k); found {
                want = slices.Delete(want, i, i+1)
            }
        } else {
            tree.Insert(k)
            if i, found := slices.BinarySearch(want, k); !found {
                want = slices.Insert(want, i, k)
            }
        }
        if tree.Contains(k) != slices.Contains(want, k) {
            t.Fatalf("Contains(%d) disagrees with the model", k)
        }
    }
    if got := slices.Collect(tree.All()); !slices.Equal(got, want) {
        t.Fatalf("in-order walk = %v, want %v", got, want)
    }
}

$ go test -v
=== RUN   TestBSTMatchesSortedSlice
--- PASS: TestBSTMatchesSortedSlice (0.00s)
PASS
ok      bst     0.004s

This style is called model-based testing, a kind of property-based testing (generate many random inputs and check a rule that must always hold). It's a very effective way to test a data structure: the model only needs to be correct, not fast, and random sequences reach odd shapes that hand-picked cases miss.

The BST in JavaScript

export class BST {
  #root = null; // # = private: only code inside the class can touch it

  constructor(compare = (a, b) => (a < b ? -1 : a > b ? 1 : 0)) {
    this.compare = compare; // like Array.prototype.sort's: <0, 0 or >0
  }

  has(key) {
    let n = this.#root;
    while (n) {
      const c = this.compare(key, n.key);
      if (c === 0) return true;
      n = c < 0 ? n.left : n.right; // smaller → left, bigger → right
    }
    return false;
  }

  insert(key) { this.#root = this.#insert(this.#root, key); }

  #insert(n, key) {
    if (!n) return { key, left: null, right: null }; // the empty spot
    const c = this.compare(key, n.key);
    if (c < 0) n.left = this.#insert(n.left, key);
    else if (c > 0) n.right = this.#insert(n.right, key);
    return n;
  }

  delete(key) { this.#root = this.#delete(this.#root, key); }

  #delete(n, key) { // §05's remove, using this.compare
    if (!n) return null;
    const c = this.compare(key, n.key);
    if (c < 0) n.left = this.#delete(n.left, key);
    else if (c > 0) n.right = this.#delete(n.right, key);
    else {
      if (!n.left) return n.right;
      if (!n.right) return n.left;
      let succ = n.right;
      while (succ.left) succ = succ.left;
      n.key = succ.key;
      n.right = this.#delete(n.right, succ.key);
    }
    return n;
  }

  // In-order walk with an explicit stack, as a generator.
  *[Symbol.iterator]() {
    const stack = [];
    let n = this.#root;
    while (n || stack.length) {
      while (n) { stack.push(n); n = n.left; } // go as far left as possible
      n = stack.pop(); // the smallest key not yet visited
      yield n.key;
      n = n.right; // then everything bigger than it
    }
  }
}

import { BST } from "./bst.mjs";

const t = new BST();
for (const k of [8, 3, 10, 1, 6, 14, 4, 7, 13]) t.insert(k);
console.log([...t].join(" "), t.has(6), t.has(5));

const byLength = new BST((a, b) => a.length - b.length || a.localeCompare(b));
for (const w of ["pear", "fig", "banana", "kiwi"]) byLength.insert(w);
console.log([...byLength]);

$ node demo.mjs
1 3 4 6 7 8 10 13 14 true false
[ 'fig', 'kiwi', 'pear', 'banana' ]

The same model-based test, with Node's built-in test runner:

import { test } from "node:test";
import assert from "node:assert/strict";
import { BST } from "./bst.mjs";

test("BST matches a Set after random ops", () => {
  let seed = 42; // a tiny fixed-seed random generator, so runs repeat
  const rand = (n) => (seed = (seed * 1103515245 + 12345) % 2 ** 31) % n;
  const tree = new BST(), model = new Set();
  for (let i = 0; i < 10_000; i++) {
    const k = rand(500);
    if (rand(3) === 0) { tree.delete(k); model.delete(k); }
    else { tree.insert(k); model.add(k); }
    assert.equal(tree.has(k), model.has(k));
  }
  assert.deepEqual([...tree], [...model].sort((a, b) => a - b)); // numeric sort!
});

$ node --test bst.test.mjs      # spec-style output in a terminal
✔ BST matches a Set after random ops (26.6ms)
ℹ tests 1
ℹ pass 1
ℹ fail 0

The trie in Go and JavaScript

type trieNode struct {
    children map[rune]*trieNode // one entry per next letter
    end      bool               // true if a word ends exactly here
}

type Trie struct{ root *trieNode }

func NewTrie() *Trie {
    return &Trie{root: &trieNode{children: map[rune]*trieNode{}}}
}

func (t *Trie) Insert(word string) {
    n := t.root
    for _, ch := range word { // ch is a rune: one Unicode character
        next, ok := n.children[ch]
        if !ok { // no path for this letter yet: create it
            next = &trieNode{children: map[rune]*trieNode{}}
            n.children[ch] = next
        }
        n = next
    }
    n.end = true // mark "a word ends here"
}

// WithPrefix returns every stored word starting with prefix, sorted.
func (t *Trie) WithPrefix(prefix string) []string {
    n := t.root
    for _, ch := range prefix { // 1. walk down the prefix
        n = n.children[ch]
        if n == nil {
            return nil // nobody starts with that
        }
    }
    var out []string
    var walk func(n *trieNode, word []rune)
    walk = func(n *trieNode, word []rune) { // 2. collect everything below
        if n.end {
            out = append(out, string(word))
        }
        for _, ch := range slices.Sorted(maps.Keys(n.children)) {
            walk(n.children[ch], append(word, ch))
        }
    }
    walk(n, []rune(prefix))
    return out
}

$ go run .            # after inserting car, card, care, cart, cat, do, dog
WithPrefix("car") → [car card care cart]
WithPrefix("ca")  → [car card care cart cat]
WithPrefix("x")   → []

In practice: choosing a sorted structure

What each language gives you

Notice that newer designs (Rust, the popular Go packages) chose B-trees, not red-black trees, even for in-memory data. Here is why.

Why databases (and newer libraries) use B-trees

A binary tree with a million keys is ~20 levels deep, and every level is a separate node somewhere in memory. Following a child pointer means loading memory you can't predict in advance — Pointer chasingPointer chasingFollowing a chain of pointers (a linked list, a tree) where you can't know the next address until you've loaded the current item. Each hop can be a full cache miss, and the CPU can't overlap them. — and each hop can stall the CPU for ~100 ns while it waits for RAM. On disk it's far worse: each hop can be a separate page read.

A B-treeB-treeA wide, shallow, always-sorted tree that most databases use for tables and indexes. Each node fills one disk page and holds hundreds of keys, so finding one row among millions takes only 3–4 page reads. puts many sorted keys in each node (a node fills a disk page, or a few CPU cache lines), so each node has hundreds of children — its fan-outFan-out (of a tree)How many children each node of a tree has. A binary tree has fan-out 2; a B-tree page holds hundreds of keys, so its fan-out is in the hundreds — which is why the tree stays only 3–4 levels tall.. A million keys then fit in 3–4 levels. Searching inside one node is a quick scan of memory that sits side by side, which the CPU handles well. Fewer hops wins, even with more comparisons per hop.

That's the whole recap here. Indexes & B-Trees §03 builds a B-tree up from scratch with page splits and a playground, and CPU Caches §10 explains the hardware side.

Two Go options, side by side

package main

import (
    "fmt"
    "slices"

    "github.com/google/btree" // go get github.com/google/btree@v1.1.3
)

type Tier struct {
    Start int // tier applies from this price (in cents) upward
    Name  string
}

func main() {
    // Option 1: sorted slice + binary search (standard library only)
    tiers := []Tier{{0, "free"}, {1000, "basic"}, {5000, "pro"}, {20000, "enterprise"}} // sorted by Start

    // The last tier with Start <= price. Assumes price >= tiers[0].Start (here: not negative).
    find := func(price int) Tier {
        i, found := slices.BinarySearchFunc(tiers, price, func(t Tier, p int) int { return t.Start - p })
        if !found {
            i-- // i is where price would be inserted; the tier before it covers price
        }
        return tiers[i]
    }
    fmt.Println(find(4999).Name, find(5000).Name, find(99999).Name) // basic pro enterprise

    // Option 2: an in-memory B-tree (github.com/google/btree, v1.1+)
    t := btree.NewOrderedG[int](32) // degree 32: up to 63 keys per node
    for _, k := range []int{50, 20, 80, 10, 30, 70, 90} {
        t.ReplaceOrInsert(k)
    }
    t.AscendRange(25, 75, func(k int) bool { // every key in [25, 75)
        fmt.Print(k, " ") // 30 50 70
        return true       // keep going
    })
    fmt.Println()
}

A benchmark: one million random int keys

Measured on this site's build machine (4-core Intel Xeon VM at 2.3 GHz, Go 1.24). Lookups probe a million random keys that exist, in random order, so caches can't hide anything. VM numbers are noisy: treat the ranges as rough.

What it shows:

• The hash map is fastest for exact lookups, by a lot — but it can't answer “next key after x” or ranges.
• The sorted slice beats both trees on lookups and uses a third of the BST's memory (and about 60% of the B-tree's): one contiguous block of 8-byte numbers, no pointers. Its weakness is inserting into the middle: every later element must shift over.
• The B-tree is the all-rounder when data changes often and you need order. It's ~2× faster than the binary tree here, with half the memory.
• Our plain BST was 50 levels tall with these random keys (versus 20 for a perfect tree) and pays a likely cache miss on nearly every level.

Trees in disguise: persistent, Merkle, interval

Persistent trees: cheap copies by sharing

In React or Redux you never mutate state in place; you produce a new state object and keep the old one. That's an ImmutableImmutableCan't be changed after it's created. To “change” an immutable value you make a new one. Immutable objects can be shared freely, because nobody can modify them under you. style. Copying a 100,000-item structure on every keystroke would be far too slow, though. The trick is a persistent data structurePersistent (immutable) data structureA data structure where an “update” returns a new version and leaves the old one untouched and still usable. Done efficiently by sharing every unchanged part between versions instead of copying it.: an update returns a new version while the old one stays valid, and the two share every part that didn't change.

For a tree this is easy. To change one leaf, copy only the nodes on the path from the root down to it — about log₂ n nodes — and let the copies point at the old, untouched subtrees. That's Structural sharingStructural sharing (path copying)How persistent trees update cheaply: copy only the nodes on the path from the root to the change (about log n of them) and point the copies at the old, unchanged subtrees.:

Where you meet it:

• Immer (the library behind Redux Toolkit's reducers) lets you write draft.items[3].done = true and produces a new object tree that shares every untouched branch with the old one.
• Clojure and Immutable.js build their vectors and maps as wide trees (32 children per node), so an update copies only a handful of small nodes.
• Undo history, time travel and snapshots come almost for free: keep the old root.
• Copy-on-write B-trees in databases and file systems (LMDB, Btrfs) apply the same idea on disk: never overwrite a page, write new copies of the path and switch the root.

The cost: more garbage for the garbage collectorGarbage collector (GC)Part of the language runtime that automatically frees memory nobody can reach anymore. Anything still referenced — like a stuck goroutine — is never freed., and an extra allocation per node on the path for every update. Fine for UI state; a real cost in a hot loop.

Merkle trees: fingerprints all the way up

A Hash functionHash functionA function that turns any input (a string, a file) into a fixed-size number or fingerprint. The same input always gives the same output, and small changes give very different outputs — used to spread keys across buckets or servers, and (with cryptographic hashes like SHA-256) to detect tampering. turns any data into a short fingerprint. A Merkle treeMerkle tree (hash tree)A tree where every leaf holds the hash of a data block and every parent holds the hash of its children's hashes. The root hash fingerprints all the data: if any block changes, the root changes, and you can find which block by following the differing hashes down. hashes every data block, then hashes pairs of hashes, and so on up to a single root hash. Change any byte anywhere and the root changes, and the path of changed hashes leads straight to the change:

That gives two superpowers: one hash proves the whole dataset is identical, and when it isn't, comparing children narrows down the difference in about log₂ n steps instead of comparing every block.

• Git names every file, directory and commit by a hash of its contents, and a directory's hash covers its children's hashes. A commit's hash therefore fingerprints the entire project. That's why git diff between two commits can skip whole folders whose hashes match.
• Replica sync. Dynamo-style databases (Cassandra, Riak) run Anti-entropyAnti-entropyA background process that compares replicas (often using hash trees) and copies over whatever is missing, so even rarely read data eventually converges.: two replicas exchange Merkle tree hashes of their data and copy only the ranges that differ, instead of shipping every row (Replication §10).
• Blockchains and certificate transparency logs put a Merkle root in each block or log entry, so you can prove one transaction or certificate is included by showing just the ~log₂ n sibling hashes on its path.

Interval and segment trees, in one paragraph

Some questions are about ranges, not keys: “which meetings overlap 2–3 pm?”, “which IP blocks contain this address?”, “what's the sum of sales from day 100 to day 900?”. An interval tree is a BST of intervals, sorted by start, where each node also remembers the largest end anywhere in its subtree; that one extra number lets a search skip subtrees that can't possibly overlap, answering in O(log n + number of matches). A segment tree splits an array into halves, quarters and so on, and stores a summary (sum, min, max) for each piece, so any range sum or minimum takes O(log n) and updating one element touches only log n summaries. Both are the same trick as Merkle trees: store a summary of each subtree in its root, so whole subtrees can be answered or skipped without visiting them.

Pitfalls gallery

u := &User{Name: "bob"}
tree.Insert(u)        // sorted by Name
u.Name = "zoe"        // tree still has it where "bob" goes
tree.Contains(u)      // false: search goes right, node is on the left

tree.Delete(u)        // take it out…
u.Name = "zoe"
tree.Insert(u)        // …and put it back

Check yourself

Predict the answer before you click. Each explanation points back to the section that covers it.

var t BST[int] // the plain BST from §09
for k := 1; k <= 1000; k++ {
    t.Insert(k)
}
fmt.Println(t.Height())

Cheat sheet