Tries

intermediateCommon atGoogleAmazonAnthropicMetaRead firstHash mapsBinary treesPractise in the Sandbox →

A trie (prefix tree, said “try”) stores strings letter by letter: each edge is one character, and the path from the root to a node spells a prefix. Words with a common prefix share that path. Insert, exact lookup and “does anything start with p?” each take O(L) steps for a key of length L, independent of how many words are stored. The price is memory: one node per distinct prefix.

The idea in plain words

Think of a paper dictionary with thumb tabs. To find “cart”, you don’t compare it with every word. You flip to C, then within C to CA, then CAR, then CART. Each letter narrows the search to a smaller section, and the number of flips depends only on the word’s length.

A trie is that tab system as a data structure. Every node answers one question: “given the letters so far, which letter comes next?” The root is the empty prefix. Each node also carries one flag, end, meaning “a whole word stops here”. You need the flag because “car” can be a stored word while also being a prefix of “cart”.

Two consequences:

• Prefix questions are free. Whether any word starts with “ca” is just “can I walk c → a?”. A hash set of words can only answer that by checking every word.
• Shared prefixes are stored once. “car”, “cart”, “care” and “cat” need 6 nodes for 14 letters.

See it

Insert words, search for whole words, and ask whether anything starts with a prefix. Watch which nodes are reused and which are created, and notice that “search word” and “starts with” walk exactly the same path; only the final check differs.

Trie sandbox: words that share a prefix share a path

interactive

word / prefix

operateinsertsearch wordstarts withdelete

words6

letters stored as words19

trie nodes (excl. root)9

current nodepath so farnew nodeend of word / foundmissing / removed

Six words: car, cart, care, cat, dog, do. Each node is one letter; the path from the root spells a prefix.

↺◀▶ Play▶1 / 1

Operation log

Try: insert "card" (3 of its 4 letters are shared), search "ca", then starts with "ca".

Things to try:

• Search for “ca”: the path exists but has no end marker, so it’s not a word. Then try starts with “ca”.
• Insert “cards” and “carton”. Count the new nodes in the log.
• Delete “cart” and watch the cleanup stop at the first node that’s still needed.

When to reach for it

The problem says…	Why a trie fits
“all words starting with…”, “type-ahead”, “prefix count”	Walk to the prefix node in O(L); everything below it is the answer set.
“check many words against many positions” (a word list searched in a grid or text)	One walk explores every word that shares the current prefix at once, and you can stop as soon as no word continues.
“longest / shortest dictionary word that is a prefix of this text”	Walk the text through the trie; each end marker you pass is a match.
“longest common prefix”, “group by prefix”	Shared prefixes are literally shared paths.
bitwise “maximum XOR with x”	A binary trie over the bits, highest bit first, lets you greedily pick the opposite bit.

When a hash set is better

If you only ever ask “is this exact word stored?”, a hash set is simpler, smaller and usually faster: hashing a string is also O(L). The trie earns its memory only when you ask prefix questions, or walk many candidate strings letter by letter.

How it works

1. Start at the root. For each character of the word, look up the child for that character.
2. Insert: if the child doesn’t exist, create it. Lookup: if it doesn’t exist, stop: no stored word has this prefix.
3. After the last character: insert sets end = true; exact search returns the end flag; prefix search returns true just for having got this far.
4. Delete: clear end, then walk back up removing nodes that have no children and no end flag. Stop at the first node still in use.

The building block every trie operation shares is the walk-and-maybe-create loop:

Python

trie_insert.py

class TrieNode:
    __slots__ = ("children", "end")       # thousands of nodes: skip the per-object __dict__

    def __init__(self) -> None:
        self.children: dict[str, TrieNode] = {}   # letter -> child
        self.end = False                           # does a whole word stop here?


def insert(root: TrieNode, word: str) -> int:
    """Add word; return how many new nodes it needed (shared prefixes cost nothing)."""
    node, created = root, 0
    for ch in word:                        # 1. one step per letter
        nxt = node.children.get(ch)
        if nxt is None:                    # 2. missing edge: create the child
            nxt = node.children[ch] = TrieNode()
            created += 1
        node = nxt                         #    existing edge: just follow it
    node.end = True                        # 3. mark where the word ends
    return created


def count_nodes(n: TrieNode) -> int:
    return 1 + sum(count_nodes(c) for c in n.children.values())


if __name__ == "__main__":
    root = TrieNode()
    assert insert(root, "car") == 3
    assert insert(root, "cart") == 1      # "car" was already paid for
    assert insert(root, "care") == 1
    assert insert(root, "cat") == 1
    assert insert(root, "car") == 0       # re-inserting changes nothing
    assert count_nodes(root) == 1 + 6     # root + c,a,r,t,e,t: 6 nodes for 14 letters
    assert root.children["c"].children["a"].children["r"].end
    assert not root.children["c"].children["a"].end   # "ca" is a prefix, not a word
    print("ok")

TypeScript

trie_insert.ts

import assert from "node:assert/strict";

export class TrieNode {
  children = new Map<string, TrieNode>(); // letter -> child
  end = false; // does a whole word stop here?
}

/** Add word; return how many new nodes it needed (shared prefixes cost nothing). */
export function insert(root: TrieNode, word: string): number {
  let node = root, created = 0;
  for (const ch of word) { // 1. one step per letter (for..of iterates code points)
    let next = node.children.get(ch);
    if (!next) { // 2. missing edge: create the child
      next = new TrieNode();
      node.children.set(ch, next);
      created++;
    }
    node = next; // existing edge: just follow it
  }
  node.end = true; // 3. mark where the word ends
  return created;
}

const countNodes = (n: TrieNode): number =>
  1 + [...n.children.values()].reduce((s, c) => s + countNodes(c), 0);

const root = new TrieNode();
assert.equal(insert(root, "car"), 3);
assert.equal(insert(root, "cart"), 1); // "car" was already paid for
assert.equal(insert(root, "care"), 1);
assert.equal(insert(root, "cat"), 1);
assert.equal(insert(root, "car"), 0); // re-inserting changes nothing
assert.equal(countNodes(root), 1 + 6); // root + c,a,r,t,e,t: 6 nodes for 14 letters
assert.equal(root.children.get("c")!.children.get("a")!.end, false); // "ca" is a prefix, not a word
console.log("ok");

C#

trie_insert.cs

var root = new TrieNode();
Expect(Insert(root, "car"), 3);
Expect(Insert(root, "cart"), 1);                 // "car" was already paid for
Expect(Insert(root, "care"), 1);
Expect(Insert(root, "cat"), 1);
Expect(Insert(root, "car"), 0);                  // re-inserting changes nothing
Expect(CountNodes(root), 1 + 6);                 // root + c,a,r,t,e,t: 6 nodes for 14 letters
if (root.Children['c'].Children['a'].End) throw new Exception("\"ca\" is a prefix, not a word");
Console.WriteLine("ok");

// Add word; return how many new nodes it needed (shared prefixes cost nothing).
static int Insert(TrieNode root, string word)
{
    var node = root;
    int created = 0;
    foreach (char ch in word)                    // 1. one step per letter
    {
        if (!node.Children.TryGetValue(ch, out var next))
        {
            next = new TrieNode();               // 2. missing edge: create the child
            node.Children[ch] = next;
            created++;
        }
        node = next;                             //    existing edge: just follow it
    }
    node.End = true;                             // 3. mark where the word ends
    return created;
}

static int CountNodes(TrieNode n) => 1 + n.Children.Values.Sum(CountNodes);

static void Expect(int got, int want) { if (got != want) throw new Exception($"got {got}, want {want}"); }

class TrieNode
{
    public readonly Dictionary<char, TrieNode> Children = []; // letter -> child
    public bool End;                                          // does a whole word stop here?
}

Lookup and prefix search are the same loop with “create” replaced by “give up”. A classic exercise that uses the trie’s shape directly: the longest common prefix of a word list is the path from the root down to the first fork or word end.

Python

common_prefix.py

class TrieNode:
    __slots__ = ("children", "end")

    def __init__(self) -> None:
        self.children: dict[str, TrieNode] = {}
        self.end = False


def longest_common_prefix(words: list[str]) -> str:
    """Longest prefix shared by every word. Classic exercise; a trie makes the shape visible."""
    if not words:
        return ""
    root = TrieNode()
    for w in words:                                  # 1. build the trie
        node = root
        for ch in w:
            node = node.children.setdefault(ch, TrieNode())
        node.end = True
    out: list[str] = []
    node = root
    # 2. walk down while the path doesn't fork and no word has ended yet
    while len(node.children) == 1 and not node.end:
        ch, node = next(iter(node.children.items()))
        out.append(ch)
    return "".join(out)                              # 3. the fork (or word end) is where they diverge


if __name__ == "__main__":
    assert longest_common_prefix(["interview", "internet", "interval"]) == "inter"
    assert longest_common_prefix(["car", "cart"]) == "car"     # stops where "car" ends
    assert longest_common_prefix(["dog", "cat"]) == ""
    assert longest_common_prefix(["solo"]) == "solo"
    assert longest_common_prefix([]) == ""
    assert longest_common_prefix(["", "a"]) == ""
    print("ok")

TypeScript

common_prefix.ts

import assert from "node:assert/strict";

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

/** Longest prefix shared by every word. Classic exercise; a trie makes the shape visible. */
export function longestCommonPrefix(words: string[]): string {
  if (words.length === 0) return "";
  const root = new TrieNode();
  for (const w of words) { // 1. build the trie
    let node = root;
    for (const ch of w) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch)!;
    }
    node.end = true;
  }
  let out = "";
  let node = root;
  // 2. walk down while the path doesn't fork and no word has ended yet
  while (node.children.size === 1 && !node.end) {
    const [ch, child] = node.children.entries().next().value!;
    out += ch;
    node = child;
  }
  return out; // 3. the fork (or word end) is where they diverge
}

assert.equal(longestCommonPrefix(["interview", "internet", "interval"]), "inter");
assert.equal(longestCommonPrefix(["car", "cart"]), "car"); // stops where "car" ends
assert.equal(longestCommonPrefix(["dog", "cat"]), "");
assert.equal(longestCommonPrefix(["solo"]), "solo");
assert.equal(longestCommonPrefix([]), "");
assert.equal(longestCommonPrefix(["", "a"]), "");
console.log("ok");

C#

common_prefix.cs

using System.Text;

Expect(LongestCommonPrefix(["interview", "internet", "interval"]), "inter");
Expect(LongestCommonPrefix(["car", "cart"]), "car");      // stops where "car" ends
Expect(LongestCommonPrefix(["dog", "cat"]), "");
Expect(LongestCommonPrefix(["solo"]), "solo");
Expect(LongestCommonPrefix([]), "");
Expect(LongestCommonPrefix(["", "a"]), "");
Console.WriteLine("ok");

// Longest prefix shared by every word. Classic exercise; a trie makes the shape visible.
static string LongestCommonPrefix(string[] words)
{
    if (words.Length == 0) return "";
    var root = new TrieNode();
    foreach (var w in words)                      // 1. build the trie
    {
        var node = root;
        foreach (char ch in w)
        {
            if (!node.Children.TryGetValue(ch, out var next)) node.Children[ch] = next = new TrieNode();
            node = next;
        }
        node.End = true;
    }
    var sb = new StringBuilder();
    var cur = root;
    while (cur.Children.Count == 1 && !cur.End)   // 2. walk while the path doesn't fork
    {
        var (ch, child) = cur.Children.First();
        sb.Append(ch);
        cur = child;
    }
    return sb.ToString();                         // 3. the fork (or word end) is where they diverge
}

static void Expect(string got, string want) { if (got != want) throw new Exception($"got '{got}', want '{want}'"); }

class TrieNode
{
    public readonly Dictionary<char, TrieNode> Children = [];
    public bool End;
}

Representing children

Children as…	Lookup	Memory per node	Use when
fixed array of 26 (or 256)	O(1), no hashing	26 pointers, mostly empty	small known alphabet, speed matters
hash map (dict, Map, Dictionary)	O(1) average	proportional to actual children	any alphabet, Unicode, the interview default
sorted list / array of pairs	O(log σ)	tight	memory-bound, read-heavy

What it costs

Let L be the key length, n the number of words, N the total letters across all words, and σ the alphabet size.

Operation	Trie	Hash set of words	Sorted list + binary search
insert	O(L)	O(L) average	O(L log n) find + O(n) shift
exact lookup	O(L)	O(L) average	O(L log n)
any word starts with p?	O(|p|)	O(N): check every word	O(|p| log n)
list all k words with prefix p	O(|p| + size of that subtree)	O(N)	O(|p| log n + k·L)
memory	O(N) nodes worst case, fewer with sharing; each node has map overhead	O(N) characters	O(N) characters

The time column is the trie’s selling point: it never depends on n. The memory column is the catch. Each node is an object with a children map, so a trie of short random strings can use several times more memory than the strings themselves. Shared prefixes help; unique tails don’t.

Variations you’ll meet

• Counts on nodes. Store how many words pass through each node and you can answer “how many words start with p?” in O(|p|). Remember to decrement on delete.
• Payload at the end node. A trie as a map: the end node holds a value (an id, a frequency, a definition).
• Compressed trie (radix tree / Patricia trie). Merge chains of single-child nodes into one edge labelled with a string. Same operations, far fewer nodes. Used in routers’ IP lookup and HTTP routing tables.
• Binary trie. Keys are integers, edges are bits. Used for “maximum XOR” and IP prefix matching.
• Suffix trie / suffix tree. Insert every suffix of a text; any substring query becomes a prefix walk. A suffix tree is the compressed version, buildable in O(n).
• Ternary search tree. Each node has less/equal/greater children: a memory-friendlier trie that behaves like a BST per character.

Pitfalls

• Forgetting the end flag. Without it, “ca” looks stored as soon as “car” is. Lookups must check end; prefix checks must not.
• Deleting too much. Removing “car” must not delete nodes that “cart” still uses. Prune bottom-up and stop at the first node with children or another word ending.
• The empty string. Is "" a valid word? Inserting it sets end on the root. Decide and say so.
• Case and Unicode. Normalize case if the problem says to. In TS, for..of iterates code points while s[i] gives UTF-16 units; pick one consistently.
• Recursion depth when collecting words under a node in a deep trie (long strings). An explicit stack avoids it.
• Memory blow-up from per-node objects. In Python, __slots__ cuts per-node overhead noticeably; a 26-slot array per node wastes space on sparse alphabets.

In the interview

• Ask about the alphabet (lowercase only? Unicode?), case sensitivity, max word length, and whether there are far more queries than inserts.
• Justify the trie over a hash set out loud: “Prefix queries would be O(N) on a set; on a trie they’re O(length of the prefix).”
• State costs in L and N, not just n.
• Expect follow-ups: “Memory is too high, what now?” (compress single-child chains, array children for small alphabets, or a sorted array with binary search on prefixes), “How do you delete?” (clear the flag, prune unused nodes), “What if the alphabet is all of Unicode?” (hash-map children, never fixed arrays).

Check yourself

Check yourself

pick one

A trie holds 1 million words. How many steps does 'does any word start with “pre”?' take, and why?

AAbout 20, because it is a balanced treeB3: one child lookup per letter of the prefix, however many words are storedC1 million: every word must be checkedDIt depends on how many words start with "pre"

Check yourself

pick one

You insert 'car' and 'cart', then delete 'cart'. Which nodes should be removed?

AAll four: c, a, r, tBOnly t: it has no children and ends no word; r still ends "car"CNone: just clear the end flag on tDr and t

Check yourself

pick one

You only need to check whether exact words are in a dictionary, with no prefix queries. Which is the better default?

AA trieBA hash setCA sorted arrayDA heap

Practice on your own

These are classic textbook exercises, not gym questions:

• Replace every word in a sentence with the shortest dictionary root that is a prefix of it.
• Count the distinct substrings of a string by inserting all its suffixes into a trie.
• Maximum XOR of any two numbers in an array, using a binary trie.
• The longest dictionary word that can be built one letter at a time from other dictionary words.
• Add “how many words start with p?” to a trie by keeping a count on every node.

Go deeper

• Sedgewick and Wayne, Algorithms §5.2, Tries: R-way tries, ternary search tries, deletion.
• cp-algorithms: Aho-Corasick: a trie plus failure links, for matching many words in one pass over a text.
• Knuth, The Art of Computer Programming Vol. 3, §6.3 “Digital Searching”: tries and Patricia.
• Python docs, __slots__: why it shrinks per-node memory.

Related

Hash maps and setsThe children map inside every node, and the alternative for exact lookups.

String manipulationPrefixes, code points and normalization.

BacktrackingTries prune a backtracking search early.

String algorithmsMatching, hashing, and multi-pattern search.