Trie (Prefix Tree) Visualization

What a trie stores

A trie (from retrieval; also called a prefix tree) stores a set of strings letter by letter. Every edge is labelled with one letter, and the string of a node is the sequence of letters on the path from the root down to it. The words themselves are not stored anywhere: the path spells them. Words that begin the same way share the beginning of their path, so CAR, CAT and CART all go through the same C and A nodes.

Each node has one child slot per letter (26 here: the page turns what you type into capital letters and drops everything that is not a letter, up to 12 letters). A path can end in the middle of another word (CAR is the start of CART), so a node also has a flag that says whether a word ends there. In the animation the root is the empty circle at the top, every other node shows the letter of the edge leading to it, green nodes are word ends (the flag is True) and white nodes are only prefixes (False).

Searching

Start at the root and follow the child for each letter of the word in turn. If a child is missing, no stored word starts this way. If all the letters are used up, the word is stored exactly when the node reached is green.

find(word):
    node = root
    for each letter c of word:
        if node.child[c] is null:
            return false                  // no stored word starts like this
        node = node.child[c]
    return node.isWord                    // the path exists; is it a whole word?

The animation runs the same loop as a recursion: it highlights the current node, removes the first letter from the string shown at the top ("Making recursive call to A child, passing in ..."), and moves to that child.

Inserting

Insertion walks the same path, creating every missing node on the way (new nodes are white), and finally marks the last node as a word end.

insert(word):
    if root is null:
        root = new node                   // the empty root: no letter
    node = root
    for each letter c of word:
        if node.child[c] is null:
            node.child[c] = new node      // white: not a word end (yet)
        node = node.child[c]
    node.isWord = true                    // turn it green

After a new node is added, the tree is laid out again: each leaf gets a fixed width, each node is centred over its children, and children are ordered A to Z.

Deleting

Find the word and clear its flag. The node may now be useless: a white node without children is not a word and leads to no word. Such nodes are removed, and the removal continues upwards until it reaches a node that is still needed because it is green or has another child.

delete(word):
    node = the node where find(word) ends
    if node is null or not node.isWord:
        return                            // not in the trie: nothing to do
    node.isWord = false                   // turn it white
    while node is not a word and has no children:
        remove node from its parent       // the root too, if the trie is now empty
        node = its parent

A worked example

Insert CAR, CAT, CART and DOG into an empty trie (a * marks a green node):

insert CAR        insert CAT        insert CART       insert DOG
(root)            (root)            (root)            (root)
 +-C               +-C               +-C               +-C
    +-A               +-A               +-A            |  +-A
       +-R*              +-R*              +-R*        |     +-R*
                         +-T*              |  +-T*     |     |  +-T*
                                           +-T*        |     +-T*
                                                       +-D
                                                          +-O
                                                             +-G*

1. CAR: the trie is empty, so the root is created, then C, A and R (all white). At the end of the word R turns green.
2. CAT: C and A already exist and are just followed. A has no T child, so one is created and marked. A now has two children: this is where CAR and CAT part.
3. CART: C, A, R all exist; a T is added below R. R stays green, because CAR is still a word even though it is no longer a leaf.
4. DOG: the root has no D child, so a new branch D, O, G is created.

Now find CA: the path exists, but A is white, so CA is not found. CARTS: the last T has no S child, so it is not found. COT fails at the first missing letter, O under C.

Delete CAR: R turns white but still has the child T, so nothing is removed. Then delete CART: its T turns white and is a leaf, so it is removed; that leaves R as a white leaf, which is removed too; A still has its T child, so the pruning stops there. The trie now holds CAT and DOG.

Print visits the children from A to Z and outputs a node's word before the words below it, so the words come out in alphabetical order: CAT DOG. To experiment with bigger tries, New random tree builds one from 10 to 50 random made-up words (listed below the tree in the order they are inserted).

Why it works

The trie keeps two facts true. A node for a string s exists exactly when s is a prefix of some stored word (insertion creates the whole path; deletion only removes nodes that no longer lead to a word). And the node is green exactly when s itself is stored. A search follows the one and only path that spells the word, so it answers correctly, and never needs to look at any other part of the tree. Because the shape depends only on the set of words, not on the order they were inserted, a trie never becomes unbalanced the way a binary search tree can.

The flag is what makes prefixes work: without it, CAR could not be told apart from "just the beginning of CART". A rule like "words end at leaves" would lose every word that is a prefix of another.

Running time and space

For a word of length L, find, insert and delete each visit at most L + 1 nodes, and each step is a single array lookup, so all three take O(L) time, no matter how many words n are stored. A balanced binary search tree of strings needs O(log n) comparisons, each of which may read up to L characters, so O(L log n). A hash table also takes O(L) expected time (to hash the word), but it cannot answer "which words start with CA?" or list the words in order. A trie answers that by walking to the node for CA and listing the words below it, in O(L + k) for k letters of output.

The price is memory. With N letters in all the words together there are at most N + 1 nodes, but every node has 26 child pointers, most of them null: O(26 N) pointers in the worst case. Shared prefixes reduce N. The variants below reduce the cost per node.

Common mistakes and edge cases

• A word that is a prefix of another (CAR and CART): the word end is a flag, not "being a leaf". A search that reaches an existing but white node has found a prefix, not a word.
• Deleting only clears a flag unless the node becomes a useless white leaf. Pruning must stop at the first node that is green or has another child, or it would delete other words. Deleting a word that is not stored (or is only a prefix, like CA) changes nothing.
• The empty string would be the root's own flag. This page ignores empty input, so the root is never green.
• Duplicates: inserting a stored word again just sets the flag again. To count occurrences, store a counter instead of a flag.
• Alphabet and case: the page maps input to the 26 capital letters. For larger alphabets (Unicode), a fixed array per node is too big; use a map or a sorted list of children instead.

Variants and uses

A radix tree merges chains of single-child nodes into one node with a string label, and a ternary search tree stores each node's children in a small binary search tree instead of an array of 26. Suffix trees are compressed tries of all the suffixes of a text, and the Aho–Corasick string-matching algorithm adds failure links to a trie of patterns to find them all in one pass over a text.

Tries are used for autocomplete (walk to the typed prefix, then list the words below it), spell checking (look words up; suggest corrections by exploring nearby paths), word games (a Boggle solver stops as soon as no word starts with the letters so far), and IP routing, where a binary trie over the bits of the addresses finds the longest matching network prefix.

References

Trie