Tries and Union-Find

Two Specialists
The Problem With Searching Prefixes
What a Trie Looks Like
Building a Trie
Autocomplete
Trie Costs and Trade-offs
The Grouping Problem
Union-Find: The Simple Version
Path Compression and Union by Rank
Connected Components and Redundant Edges
Recipe: trie.ts and union-find.ts for algolab
Try It Yourself

1. Two Specialists

Most of the structures so far are generalists. Arrays, hash maps, trees and graphs show up in nearly every program. This chapter covers two specialists. Each does one job so well that it is worth knowing by name:

A trie (say "try", from retrieval) stores many strings so that "everything that starts with ca" is fast. It powers autocomplete, spell checkers, and the routing table inside many web frameworks.
A union-find (also called a disjoint-set union, or DSU) keeps track of which items belong to the same group, and merges groups quickly. It answers "are these two connected?" in nearly constant time. You meet it in network connectivity, friend groups, image segmentation, and Kruskal's minimum-spanning-tree algorithm.

Neither is exotic. A search box with suggestions is a trie problem. "Are these two users in the same team after these merges?" is a union-find problem. Both are also favorites in interviews, because the trick behind each is short and elegant.

2. The Problem With Searching Prefixes

You are building a search box. The user types ca, and you want to show words that start with it. You have 100,000 words. The obvious solution:

function startingWith(words: string[], prefix: string): string[] {
  return words.filter((w) => w.startsWith(prefix));
}

const words = ["car", "card", "care", "cat", "dog"];
console.log(startingWith(words, "ca"));
// [ 'car', 'card', 'care', 'cat' ]

It works, but it looks at every word on every keystroke. That is O(n × L), where n is the number of words and L is the prefix length. With 100,000 words and a keystroke every 100 ms, you are doing a lot of repeated work to answer a question whose answer barely changes between keystrokes.

Could a hash map help? A Set answers "is car a word?" in O(1), but it cannot answer "which words start with ca?" without scanning everything. Hashing scrambles the words, so the neighbors are lost.

A sorted array plus binary search (chapter 7) finds the first word with the prefix in O(L log n), and the matches sit next to each other. That is good, but inserting a new word costs O(n) because of the shifting you learned about in the arrays chapter.

A trie gives us fast prefix search and cheap inserts.

3. What a Trie Looks Like

A trie is a tree where each edge is a letter. A word is a path from the root down to a marked node. Words that share a beginning share a path. Here are car, card, care, cat and dog:

(root)
 ├─ c
 │   └─ a
 │       ├─ r *        <- "car" ends here
 │       │   ├─ d *    <- "card"
 │       │   └─ e *    <- "care"
 │       └─ t *        <- "cat"
 └─ d
     └─ o
         └─ g *        <- "dog"

The * marks "a word ends here". We need it because car is both a word and the beginning of card. Without the mark we could not tell that car was stored, while ca was not.

Notice the saving: car, card and care store the letters c, a, r only once. And to find everything starting with ca, you walk two steps (c, then a) and then everything below that node is an answer. You never look at dog at all.

Question	How a trie answers it
Is `card` a word?	Follow `c`, `a`, `r`, `d`. Is the last node marked?
Does anything start with `ca`?	Follow `c`, `a`. Did the path exist?
Which words start with `ca`?	Follow `c`, `a`, then collect every marked node below.

Each step down is a lookup of one letter among the node's children. We store the children in a Map, so each step is O(1).

4. Building a Trie

Each node needs two things: its children (letter to node) and a flag saying whether a word ends here.

class TrieNode {
  children = new Map<string, TrieNode>();
  isWord = false;
}

The trie itself is just a root node plus methods. Insert walks down the word, creating missing nodes as it goes, then marks the last one:

class Trie {
  private root = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      let next = node.children.get(ch);
      if (!next) {
        next = new TrieNode();
        node.children.set(ch, next);
      }
      node = next;
    }
    node.isWord = true;
  }
}

Both has and startsWith need to walk down a string and report where they ended. We write that walk once, as a private helper:

  private find(prefix: string): TrieNode | undefined {
    let node: TrieNode | undefined = this.root;
    for (const ch of prefix) {
      node = node.children.get(ch);
      if (!node) return undefined;
    }
    return node;
  }

  has(word: string): boolean {
    return this.find(word)?.isWord === true;
  }

  startsWith(prefix: string): boolean {
    return this.find(prefix) !== undefined;
  }

The difference between the two is the whole point of the isWord flag. has("ca") walks the path fine, but the node is not marked, so the answer is false. startsWith("ca") only cares that the path exists, so the answer is true.

With car, card, care, careful, cat and dog inserted:

console.log(t.has("car"));        // true
console.log(t.has("ca"));         // false
console.log(t.startsWith("ca"));  // true
console.log(t.startsWith("cx"));  // false

Every operation touches one node per letter. The cost depends on the length of the word, not on how many words are stored. A trie with ten words and a trie with ten million words answer has("car") in the same three steps.

5. Autocomplete

To suggest completions, walk down to the node for the prefix, then collect every word below it with a depth-first search (chapter 9), carrying the letters so far:

  suggest(prefix: string, limit = Infinity): string[] {
    const start = this.find(prefix);
    const out: string[] = [];
    if (!start) return out;

    const walk = (node: TrieNode, path: string): void => {
      if (out.length >= limit) return;
      if (node.isWord) out.push(path);
      const keys = [...node.children.keys()].sort();
      for (const k of keys) walk(node.children.get(k)!, path + k);
    };

    walk(start, prefix);
    return out;
  }

Three details worth noticing:

If the prefix does not exist, find returns undefined and we return an empty list at once. No scanning.
We check node.isWord before visiting children. That is a preorder walk, so shorter words (car) come before longer ones (card).
We sort the child letters, so the suggestions come out in alphabetical order. The limit stops early, which matters: a search box wants the first 5 suggestions, not 50,000.

console.log(t.suggest("car"));
// [ 'car', 'card', 'care', 'careful' ]

console.log(t.suggest("ca", 3));
// [ 'car', 'card', 'care' ]

console.log(t.suggest("x"));
// []

Real autocomplete usually ranks suggestions by popularity, not by alphabet. A common upgrade is to store a count in each marked node, then use a heap (chapter 10) to keep the top K matches. The structure stays the same.

6. Trie Costs and Trade-offs

Let L be the length of the word or prefix, and k the number of suggestions you collect.

Operation	Trie	Sorted array	Hash set
Insert a word	O(L)	O(n) (shifting)	O(L) (hashing the string)
Has a word?	O(L)	O(L log n)	O(L)
Any word with this prefix?	O(L)	O(L log n)	O(n × L)
List words with this prefix	O(L + size of the subtree)	O(L log n + k)	O(n × L)

Hashing a string reads every character, so a hash set lookup is also O(L). The trie is not faster for exact matches. Its win is prefix questions.

The cost is memory. Every node is an object holding a Map. A trie over a large word list can take far more memory than the same words in a Set. Ways to reduce it:

Compressed tries (radix trees) merge chains of single-child nodes into one edge labeled "reful". Many HTTP routers use this.
For lowercase a-z only, each node can hold a fixed array of 26 children instead of a Map. That is faster but wastes space on sparse nodes.
If you only need a few thousand strings, a plain sorted array and startsWith is simpler and fast enough. Reach for a trie when the word list is large, changes, or the prefix is queried constantly.

Other places a trie shows up: spell checkers ("did you mean...?"), IP routing (longest-prefix match on binary digits), T9 phone keyboards, and word games like Boggle, where you prune a search the moment no word starts with the current letters.

7. The Grouping Problem

Now a different kind of problem. You have 10 computers on a network. Cables are plugged in one at a time. After each cable, you are asked: "Can computer 3 reach computer 8?"

You could model this as a graph (chapter 11) and run BFS for each question. That costs O(V + E) per question. If there are a million cables and a million questions, that is far too slow.

But notice what we actually need to know. We do not need the path, only whether the two computers are in the same group. And groups only ever merge; a cable never splits a group.

That is the exact job of union-find. It supports two operations:

union(a, b): merge the group of a with the group of b.
find(a): return a representative (the "root") for the group of a. Two items are in the same group when they have the same representative.

Where you meet this at work:

Networks: are two machines connected after these links?
Social features: friend groups, "people you may know" clusters.
Image editing: the paint bucket tool finds the connected region of similar pixels.
Kruskal's algorithm: build a cheapest network by adding the cheapest edge that does not form a cycle. Union-find detects the cycle.
Equivalence: "these two accounts are the same person" merges in data cleaning.

8. Union-Find: The Simple Version

The idea: every item points to a parent. Following parents leads to a root, an item that points to itself. The root is the group's representative.

Start with 6 items, each in its own group, each its own parent:

parent = [0, 1, 2, 3, 4, 5]

union(0, 1) finds the roots of 0 and 1, then makes one point to the other: parent[1] = 0.

parent = [0, 0, 2, 3, 4, 5]     groups: {0,1} {2} {3} {4} {5}

union(1, 2): the root of 1 is 0, the root of 2 is 2. Point 2 to 0:

parent = [0, 0, 0, 3, 4, 5]     groups: {0,1,2} {3} {4} {5}

A first version in code:

function find(parent: number[], x: number): number {
  while (parent[x] !== x) x = parent[x];
  return x;
}

function union(parent: number[], a: number, b: number): void {
  parent[find(parent, a)] = find(parent, b);
}

This is correct, but it has a hidden problem. Union items in a bad order and the parent links form a long chain, which is a linked list in disguise:

const parent = Array.from({ length: 5 }, (_, i) => i);
for (let i = 0; i < 4; i++) union(parent, i, i + 1);
console.log(parent); // [ 1, 2, 3, 4, 4 ]

Here 0 -> 1 -> 2 -> 3 -> 4. Now find(0) walks the whole chain, which is O(n). With a million items, every query is slow. Two small ideas fix it.

9. Path Compression and Union by Rank

Idea 1: path compression. While walking up to the root during find, make every item you pass point to a grandparent (or directly to the root). The next find on that path is shorter. The tree flattens itself over time, for free, as a side effect of asking questions.

Idea 2: union by rank. When merging two trees, attach the shorter tree under the taller one, not the other way around. We keep a number rank for each root, which is an upper bound on its tree's height. If the ranks are equal, pick either and increase its rank by one.

Together these make the cost per operation almost O(1). The exact bound is O(α(n)), where α is the inverse Ackermann function. It grows so slowly that it is below 5 for any n you will ever store, even more items than there are atoms in the universe. In practice you can read it as "constant".

Here is the complete class:

class UnionFind {
  private parent: number[];
  private rank: number[];
  count: number; // number of separate groups

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.count = n;
  }

  find(x: number): number {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]]; // path halving
      x = this.parent[x];
    }
    return x;
  }

  union(a: number, b: number): boolean {
    const ra = this.find(a);
    const rb = this.find(b);
    if (ra === rb) return false; // already in the same group

    if (this.rank[ra] < this.rank[rb]) this.parent[ra] = rb;
    else if (this.rank[ra] > this.rank[rb]) this.parent[rb] = ra;
    else {
      this.parent[rb] = ra;
      this.rank[ra]++;
    }
    this.count--;
    return true;
  }

  connected(a: number, b: number): boolean {
    return this.find(a) === this.find(b);
  }
}

A few notes on the code:

The line this.parent[x] = this.parent[this.parent[x]] is called path halving. It is the loop-based cousin of path compression: each step makes x skip one level. It avoids recursion, so no stack-overflow worry on very deep trees.
union returns true when it merged two groups and false when they were already together. That small return value is surprisingly useful, as the next section shows.
count starts at n and drops by one for every successful merge. It is always the current number of groups, in O(1).

Using it:

const uf = new UnionFind(6);
console.log(uf.count);                                  // 6
console.log(uf.union(0, 1), uf.union(1, 2), uf.union(0, 2));
// true true false
console.log(uf.connected(0, 2), uf.connected(0, 5), uf.count);
// true false 4

The third union(0, 2) returns false because 0 and 2 were already joined through 1. After two real merges, six groups became four.

Operation	Naive	With rank and compression
`find`	O(n) worst	almost O(1)
`union`	O(n) worst	almost O(1)
`connected`	O(n) worst	almost O(1)
Memory	O(n)	O(n)

Union-find has one limit: it cannot split a group. It also does not remember the path between two items, only whether they are connected. If you need either, use a graph.

10. Connected Components and Redundant Edges

Here are two classic interview problems that union-find solves in a few lines.

Number of connected components. You have n nodes numbered 0 to n - 1 and a list of undirected edges. How many separate groups are there?

function countComponents(n: number, edges: [number, number][]): number {
  const uf = new UnionFind(n);
  for (const [a, b] of edges) uf.union(a, b);
  return uf.count;
}

console.log(countComponents(5, [[0, 1], [1, 2], [3, 4]])); // 2
console.log(countComponents(6, [[0, 1], [1, 2], [3, 4]])); // 3

In the first call, {0,1,2} and {3,4} make 2 groups. In the second, node 5 has no edges and is alone, so there are 3 groups. You could solve this with DFS from chapter 11, too. Union-find shines when edges arrive one at a time and you need the answer after each one, because count is always up to date.

Redundant connection. A network started as a tree with nodes 1 to n, with n - 1 links. Then one extra link was added, creating a cycle. Find the link that is the extra one: the first edge in the list whose two ends are already connected.

function findRedundantEdge(
  edges: [number, number][],
): [number, number] | null {
  const uf = new UnionFind(edges.length + 1); // nodes are 1..n
  for (const [a, b] of edges) {
    if (!uf.union(a, b)) return [a, b];
  }
  return null;
}

console.log(findRedundantEdge([[1, 2], [1, 3], [2, 3]]));
// [ 2, 3 ]
console.log(findRedundantEdge([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]));
// [ 1, 4 ]

In the first example, links 1-2 and 1-3 join everything. The link 2-3 connects two nodes that are already in the same group, so it closes a cycle. In the second example, 1-2, 2-3, 3-4 build a chain, and 1-4 connects the two ends of it. This is exactly why union returns a boolean: "did this edge connect two different groups?" is the same question as "does this edge avoid a cycle?". Kruskal's algorithm uses the same check to pick edges.

How do you spot a union-find problem? Look for these signals:

"Are X and Y connected / in the same group / equivalent?"
Groups only merge over time, never split.
You need the number of groups, or the size of the biggest.
Edges or relations arrive in a stream.

11. Recipe: trie.ts and union-find.ts for algolab

Add a trie module. Create src/trie.ts:

class TrieNode {
  children = new Map<string, TrieNode>();
  isWord = false;
}

export class Trie {
  private root = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      let next = node.children.get(ch);
      if (!next) {
        next = new TrieNode();
        node.children.set(ch, next);
      }
      node = next;
    }
    node.isWord = true;
  }

  private find(prefix: string): TrieNode | undefined {
    let node: TrieNode | undefined = this.root;
    for (const ch of prefix) {
      node = node.children.get(ch);
      if (!node) return undefined;
    }
    return node;
  }

  has(word: string): boolean {
    return this.find(word)?.isWord === true;
  }

  startsWith(prefix: string): boolean {
    return this.find(prefix) !== undefined;
  }

  suggest(prefix: string, limit = Infinity): string[] {
    const start = this.find(prefix);
    const out: string[] = [];
    if (!start) return out;

    const walk = (node: TrieNode, path: string): void => {
      if (out.length >= limit) return;
      if (node.isWord) out.push(path);
      const keys = [...node.children.keys()].sort();
      for (const k of keys) walk(node.children.get(k)!, path + k);
    };

    walk(start, prefix);
    return out;
  }
}

Add the union-find module. Create src/union-find.ts:

export class UnionFind {
  private parent: number[];
  private rank: number[];
  count: number;

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.count = n;
  }

  find(x: number): number {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }

  union(a: number, b: number): boolean {
    const ra = this.find(a);
    const rb = this.find(b);
    if (ra === rb) return false;

    if (this.rank[ra] < this.rank[rb]) this.parent[ra] = rb;
    else if (this.rank[ra] > this.rank[rb]) this.parent[rb] = ra;
    else {
      this.parent[rb] = ra;
      this.rank[ra]++;
    }
    this.count--;
    return true;
  }

  connected(a: number, b: number): boolean {
    return this.find(a) === this.find(b);
  }
}

export function countComponents(
  n: number,
  edges: [number, number][],
): number {
  const uf = new UnionFind(n);
  for (const [a, b] of edges) uf.union(a, b);
  return uf.count;
}

export function findRedundantEdge(
  edges: [number, number][],
): [number, number] | null {
  const uf = new UnionFind(edges.length + 1);
  for (const [a, b] of edges) {
    if (!uf.union(a, b)) return [a, b];
  }
  return null;
}

Now the tests. Create src/trie.test.ts:

import { test } from "node:test";
import assert from "node:assert/strict";
import { Trie } from "./trie.ts";

function build(): Trie {
  const t = new Trie();
  for (const w of ["car", "card", "care", "careful", "cat", "dog"]) {
    t.insert(w);
  }
  return t;
}

test("has distinguishes words from prefixes", () => {
  const t = build();
  assert.equal(t.has("car"), true);
  assert.equal(t.has("ca"), false);
  assert.equal(t.has("cars"), false);
});

test("startsWith checks the path only", () => {
  const t = build();
  assert.equal(t.startsWith("ca"), true);
  assert.equal(t.startsWith("cx"), false);
});

test("suggest returns sorted completions", () => {
  const t = build();
  assert.deepEqual(t.suggest("car"), ["car", "card", "care", "careful"]);
  assert.deepEqual(t.suggest("ca", 3), ["car", "card", "care"]);
  assert.deepEqual(t.suggest("x"), []);
});

And src/union-find.test.ts:

import { test } from "node:test";
import assert from "node:assert/strict";
import {
  UnionFind,
  countComponents,
  findRedundantEdge,
} from "./union-find.ts";

test("union merges groups and reports repeats", () => {
  const uf = new UnionFind(6);
  assert.equal(uf.union(0, 1), true);
  assert.equal(uf.union(1, 2), true);
  assert.equal(uf.union(0, 2), false);
  assert.equal(uf.connected(0, 2), true);
  assert.equal(uf.connected(0, 5), false);
  assert.equal(uf.count, 4);
});

test("countComponents", () => {
  assert.equal(countComponents(5, [[0, 1], [1, 2], [3, 4]]), 2);
  assert.equal(countComponents(6, [[0, 1], [1, 2], [3, 4]]), 3);
});

test("findRedundantEdge", () => {
  assert.deepEqual(findRedundantEdge([[1, 2], [1, 3], [2, 3]]), [2, 3]);
  assert.equal(findRedundantEdge([[1, 2], [2, 3]]), null);
});

Run them:

npx tsx --test

All the tests should pass. If a test fails, read the message: it shows the expected and the actual value side by side.

12. Try It Yourself

Delete from a trie. Add a remove(word) method that unmarks the word. Then improve it: also delete nodes that are no longer on the path of any word. Why must you be careful not to delete car when removing card, and not to delete card when removing car?
Count words. Add a countWithPrefix(prefix) method that returns how many stored words start with the prefix. Hint: store a counter in each node that goes up on every insert that passes through it, and the answer becomes O(L).
Longest common prefix. Given ["flower", "flow", "flight"], the answer is "fl". Solve it by inserting all words into a trie and walking down while the current node has exactly one child and is not a word end. (Interview classic.)
Word dictionary with wildcards. Support search("c.t"), where . matches any one letter. Hint: when you see ., try every child with recursion (chapter 6).
Size of the biggest group. Extend UnionFind with a size array so that sizeOf(x) returns how many items are in the group of x. Update it inside union. Test with 6 items and a few merges.
Accounts merge. Each account has a name and emails. Two accounts with a shared email belong to the same person. Use union-find on the account indexes, with a Map from email to the first account index that used it, to group them. (Interview-style, medium.)

A trie answers prefix questions by letting words share their beginnings. Union-find answers "are these connected?" by letting groups share one representative. In the next chapter, Greedy and Dynamic Programming, we step away from structures and look at two ways of designing algorithms: always taking the best-looking choice right now, and remembering the answers to smaller problems so they are never solved twice.