Tries (Prefix Trees): Autocomplete, Prefix Search, and When the Path Is the Key

In plain words

A trie is like a physical dictionary where every page, shelf, and section is labeled with successive letters of the alphabet. Finding 'algorithm' means: go to the 'a' section, then 'al', then 'alg', ... until you reach the entry. You never compare 'algorithm' against 'binary' or 'search' — you simply navigate the physical structure of the dictionary. That's a trie: navigation replaces comparison, and the location in the structure *is* the key.

The trie (from retrieval; often said 'try' to distinguish it from tree) is a specialized tree for storing strings — or any keys that are sequences of symbols. Its defining idea flips how we've stored data so far: instead of putting a key *in* a node, the trie spells the key out *along the path* from the root. That single reframing makes prefix questions — 'which stored words start with sun?' — natural, which is why tries sit behind autocomplete, spell-checkers, IP routing tables, and dictionary features.

Structure: the path is the key

Each node represents a prefix. The root is the empty prefix; each edge is labeled with one character; a node's children are keyed by the next character (an array of size = alphabet, or a small hash map per node). Following the path r → o → o → t spells 'root'. Crucially, a node carries an end-of-word flag so the trie can tell that 'sun' is a stored word even though the path continues to 'sunday' — without the flag you couldn't distinguish a stored word from a mere prefix of longer words.

Shared prefixes are stored once. Insert 'car', 'card', 'care', 'cat' and the 'ca' prefix is a single two-edge path that all four share, branching only where the words diverge. This prefix-sharing is the source of both the trie's power (cheap prefix queries) and its main cost consideration (many nodes when words *don't* share prefixes).

root
├── c
│   └── a
│       ├── r [*]         ← "car" ends here
│       │   ├── d [*]     ← "card"
│       │   └── e [*]     ← "care"
│       └── t [*]         ← "cat"
└── s
    └── u
        └── n [*]         ← "sun"
            └── d
                └── a
                    └── y [*]  ← "sunday"

[*] = end-of-word flag set

Key observations:
  • "car", "card", "care" share the c→a→r prefix (3 chars, 1 path).
  • "sun" and "sunday" share 3 characters; the flag on "n" marks "sun".
  • Searching "sun": root→s→u→n → found flag → YES (1 node per char = 3 steps).
  • startsWith("ca"): root→c→a → reached → YES, any word continues from here.

class TrieNode:
    children: Map<char, TrieNode>  // or array of size 26
    is_end:   bool = false

class Trie:
    root = TrieNode()

    def insert(word):
        node = root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = true      // mark word end

    def search(word) -> bool:
        node = root
        for ch in word:
            if ch not in node.children: return false
            node = node.children[ch]
        return node.is_end      // must be a word, not just a prefix

    def startsWith(prefix) -> bool:
        node = root
        for ch in prefix:
            if ch not in node.children: return false
            node = node.children[ch]
        return true             // reached end of prefix — success

Operations, step by step

1. insert(word): start at the root. For each character, follow the matching child edge, creating a new node if it's absent. After the last character, set that node's end-of-word flag. O(L) time.
2. search(word): walk the path character by character. If any edge is missing, the word isn't present. If you consume the whole word, it's a stored word only if the final node's end-of-word flag is set. O(L).
3. startsWith(prefix): identical to search, but success is simply reaching the end of the prefix path — no end-of-word flag needed. O(P) in the prefix length. This is the trie's signature query.
4. autocomplete(prefix): walk to the prefix node (O(P)), then do a DFS from there collecting every path that hits an end-of-word flag. O(P + size of the returned subtree).
5. delete(word): unset the end-of-word flag; then prune upward any now-childless, non-word nodes. O(L).

Worked example: autocomplete 'ca'

Phase 1: Walk to the 'ca' prefix node.
  root → c (found) → a (found) → arrived at prefix node for "ca"
  Cost: O(2) = O(P)

Phase 2: DFS from the "ca" node, collecting end-of-word paths.
  "ca" node → children: {r, t}

  Branch r: "car" node → is_end=true → collect "car"
    Continue → children: {d, e}
    Branch d: "card" node → is_end=true → collect "card"
    Branch e: "care" node → is_end=true → collect "care"

  Branch t: "cat" node → is_end=true → collect "cat"

Results: [car, card, care, cat]
Total cost: O(P + subtree_size) = O(2 + 4) = O(6)

No words NOT starting with "ca" were ever examined.

Complexity: independent of dictionary size

The headline: trie operations depend on the key's length, not the number of keys. A hash table matches on exact lookup but collapses on prefix queries — it would have to scan every stored word, because hashing scatters 'sun' and 'sunday' to unrelated buckets. The trie also yields keys in sorted order for free (DFS visiting children in alphabetical order), like a BST but keyed by shared prefixes. The cost is space: a naive trie allocates a child slot per possible character per node, and words with few shared prefixes create many sparse nodes — so a trie can use far more memory than a hash set of the same words.

Taming the space cost

• Map-based children. Store each node's children in a small hash map instead of a fixed alphabet-sized array, so unused characters cost nothing. Trades a bit of per-hop constant time for large memory savings on sparse tries.
• Compressed trie (radix tree / Patricia trie). Collapse any chain of single-child nodes into one edge labeled with the whole substring. A trie storing only 'internationalization' becomes essentially one edge, not twenty nodes. Compressed tries are what real IP routing tables and many string indexes use.
• Ternary search trees. A hybrid that stores characters in BST-like nodes with three children (less/equal/greater), trading a little query speed for much lower memory than array-child tries.

Standard trie:           Compressed (radix) trie:
root                      root
└─c                       └─"ca"
  └─a                         ├─"r" [*]
    ├─r [*]                   │   ├─"d" [*]
    │  ├─d [*]                │   └─"e" [*]
    │  └─e [*]                └─"t" [*]
    └─t [*]

Single-child chains collapsed into one labeled edge.
"ca" is a 2-char edge replacing 2 single-char nodes.
For long words with no shared prefixes, this saves dramatically.

Where tries shine

• Autocomplete and type-ahead: the canonical use — walk to the prefix, enumerate the subtree, optionally rank by stored frequency.
• Spell-check and fuzzy matching: tries support prefix-guided edit-distance search, pruning whole branches that can't be within the allowed distance.
• IP routing (longest-prefix match): routers store network prefixes in a (compressed) bit-trie and match the longest prefix of a destination address — a task tries are purpose-built for.
• Word games and dictionary validation, T9/keypad input, and multi-pattern search (the Aho-Corasick automaton is a trie augmented with failure links, generalizing KMP to many patterns at once).

Common pitfalls

• Omitting the end-of-word flag. Without it you can't tell a stored word from a prefix of a longer one — 'sun' present, or just on the way to 'sunday'? The flag is mandatory, not optional.
• Fixed-alphabet arrays for sparse data. A 26- (or 128-, or 65,536-) slot array per node wastes enormous memory when most slots are empty. Use map-based children or compression.
• Reaching for a trie when a hash set suffices. If you only ever do exact lookups and never prefix queries, a hash set is simpler and more memory-efficient. The trie earns its overhead *specifically* through prefix and ordered operations.
• Forgetting to prune on delete. Just clearing the flag leaves dead nodes that leak memory over time; prune childless non-word nodes back up the path.

Practice problems

1. Word search with prefixes. Given a 2D grid of letters and a list of words, find all words that appear in the grid (any path of adjacent cells). Hint: build a trie of the word list; DFS the grid tracking the current trie node to prune branches early when no word starts with the current path.
2. Count words with a given prefix. Augment each trie node with a count of words passing through it (increment on every insert). Then startsWith becomes O(P) and returns the count directly — no DFS needed.
3. Replace words with root. Given a dictionary of root words and a sentence, replace each word in the sentence with the shortest root that is its prefix. Build a trie from the roots; for each word, walk the trie and stop at the first end-of-word flag found. O(L) per word.

Key takeaways

• A trie stores keys along root-to-node paths, sharing common prefixes and marking word-ends with a flag.
• Insert and search are O(L) in the key length — independent of how many keys are stored.
• Prefix queries and autocomplete are the trie's superpower; hash tables can't do them without a full scan.
• The trade-off is memory: use map-based children or compressed (radix/Patricia) tries to keep space reasonable.
• Reach for a trie when prefixes, ordering, or longest-prefix matching matter; reach for a hash set when only exact lookup does.

That completes the tree family. The course now turns to the most general structure of all — where nodes connect freely, cycles are allowed, and hierarchy dissolves into networks: graphs and their representations. Practice trie and autocomplete questions in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play