Pointer Walk

Tries

A tree where each step down is one letter. Words that start the same share a path, which makes finding everything with a prefix nearly free.

Data StructuresIntermediate8 min read

Words that start the same

You type "ca" into a search box and it instantly suggests "car", "cart" and "cat". Behind that is a question a hash table cannot answer well: which stored words begin with these letters?

A hash table can tell you whether "cat" is stored. It cannot find words near "cat", because hashing scatters similar words to unrelated places. A sorted list can do it with some searching. A trie is built for exactly this.

The name comes from retrieval. It is usually pronounced "try".

A tree of letters

In a trie, a word is not stored in one place. It is spelled out along a path.

  1. Start at an empty root

    It stands for "nothing typed yet".

  2. Each step down adds one letter

    The node you reach stands for everything typed so far.

  3. Mark the nodes where a complete word ends

    The path to "car" passes through "c" and "ca". Only "car" is marked.

  4. Words with the same beginning share that part of the path

    "car" and "cat" share "c" and "a", then split.

A trie of five wordsInteractive
start
  • the path just walked
  • end of a word
  • a word found by the search

Start. An empty trie: just a root. Each step down from here will stand for one letter.

Nodes
1
Letters in all the words
15

Five words with 15 letters between them fit in 9 nodes, because the common beginnings are stored once.

Why prefix search is nearly free

To find everything starting with "ca":

  1. Walk down c, then a. Two steps.
  2. Every word below that node starts with "ca". Collect them.

The walk takes one step per letter typed. It does not depend on how many words are stored. A trie holding every word in the language answers "ca" in the same two steps.

Example

Looking up one word

Is "cart" stored? Follow c, a, r, t. Four steps, and the last node is marked: yes.

Is "ca" stored? Follow c, a. The node exists but is not marked: "ca" is only the beginning of other words.

Is "cow" stored? Follow c, then look for o. There is no such branch: no, and you found out after two letters.

Lookup time depends on the length of the word, not on the number of words.

python
class TrieNode:
    def __init__(self):
        self.children = {}        # letter -> TrieNode
        self.is_word = False

def insert(root, word):
    node = root
    for letter in word:
        node = node.children.setdefault(letter, TrieNode())
    node.is_word = True

def starts_with(root, prefix):
    node = root
    for letter in prefix:
        if letter not in node.children:
            return None           # nothing starts with this
        node = node.children[letter]
    return node                   # everything below here matches

What it costs

Good at

  • Finding all words with a given prefix takes one step per letter of the prefix
  • Looking up a word takes one step per letter, however many words are stored
  • Words come out in alphabetical order for free
  • Shared beginnings are stored once

Where it bites

  • Uses a lot of memory: a node for every letter of every distinct path, each with its own links
  • Nodes are scattered in memory, so walking them is slower than scanning an array
  • For plain exact lookups, a hash table is simpler and faster

Compact versions exist that merge chains of single-child nodes into one node holding several letters. These are called radix trees or compressed tries, and they are what most real systems use.

Where you will meet it

  • Autocomplete and search suggestions.
  • Spell checkers: is this a word, and what words are close to it?
  • Routing in networks. A router picks where to send a packet by finding the longest stored prefix that matches its address. That is a walk down a trie of bits.
  • Phone keypads and word games: which words can be made from these letters?
  • URL routing in web frameworks: matching /users/42/orders against the registered paths.

Key takeaways

  • A trie stores words as paths, with one letter for each step down.
  • Words that begin the same way share the start of their path.
  • Finding every word with a given prefix means walking down the prefix and collecting what is below.
  • Lookup time depends on the word's length, not on how many words are stored.
  • The cost is memory, so use a trie when prefix questions matter and a hash table when they do not.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress