Tries

1The mental model (what this really is)#

A Trie is a tree where each edge is a character, and each path from the root spells out a prefix.

Picture it walking down the tree.

• The root means "empty string."
• Follow an edge labeled c and you are at the node for "c".
• Follow another labeled a and you are at "ca".
• Keep going and you spell "cat".
• Words that share a prefix share the same path until they split.

So "cat", "car", and "card" overlap:

• All three walk the same c -> a path.
• "cat" branches off at t.
• "car" and "card" stay together one more step before "card" adds a d.

Here is that split drawn out so the sharing is obvious:

Each node needs exactly two things:

• A map from character to child node.
• A boolean flag that says "a word ends here."

The whole point:

• A Trie answers "does any word start with this prefix?" in time proportional to the length of the prefix.
• It does not matter how many words you stored.
• Store a million words, query "car", and you still touch exactly 3 nodes.
• A hash set of strings cannot do this. It tells you if an exact string exists, but hashing "car" tells you nothing about which stored strings start with "car".

2How to recognize it (the signals in a problem)#

Train your eyes on these. When you see them, a Trie should be the first tool you reach for, before you write a single line.

• The word prefix appears, or the problem asks about words that start with something.
• Many lookups against a fixed dictionary of words, where plain hashing is not enough because you need partial or prefix matching.
• Autocomplete, search suggestions, or "type-ahead" behavior.
• Matching with wildcards where a . can mean any single character.
• A word-search on a grid where you check many words at once against a board.
• Finding the longest common prefix, or the shortest unique prefix, across a set of strings.
• Anything about an XOR of numbers being maximized. (Yes, really. Bits are a 2-character alphabet over 0 and 1, so a binary Trie applies. More in section 5.)

The clearest tell is one combination:

• A set of strings plus shared-prefix questions asked repeatedly.
• One lookup? Use a hash set.
• Thousands of prefix queries against the same word list? Build a Trie once, then each query is cheap.

3The template (how it works, with pseudocode)#

This is the structure to write from memory. Learn this shape and you can reproduce it cold under pressure, which matters because the real problem is usually one twist bolted onto this skeleton.

class TrieNode:
    children = {}      # char -> TrieNode
    is_end = False     # true if a word ends at this node

class Trie:
    root = new TrieNode()

    insert(word):
        node = root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = new TrieNode()
            node = node.children[ch]
        node.is_end = True

    search(word):        # exact word match
        node = walk(word)
        return node != null and node.is_end

    startsWith(prefix):  # any word with this prefix?
        return walk(prefix) != null

    walk(s):             # follow s, return end node or null
        node = root
        for ch in s:
            if ch not in node.children:
                return null
            node = node.children[ch]
        return node

Three operations, one helper:

• insert carves the path and plants the end flag.
• walk follows a string as far as it can go, returning the node it lands on or null the moment a character is missing.
• search is walk plus an is_end check.
• startsWith is just walk with a null check.

If you can write these four from scratch, you can solve most Trie problems by adding one twist on top. Budget about 5 minutes to produce this clean, which leaves the rest of the round for the actual twist.

4A worked example (walk through one problem step by step)#

The classic: Word Search II. You are given a 2D grid of letters and a list of words. Return every word from the list that can be formed by a path of adjacent cells (up, down, left, right), using each cell at most once per word.

Why the naive approach is too slow:

• Run a separate DFS on the grid for each word.
• 10,000 words means 10,000 full grid searches.
• You re-walk the same grid prefixes over and over, so "oath" and "oats" each pay the full cost of exploring o -> a -> t from scratch.

The insight:

• Build one Trie of all the words.
• Do a single DFS over the grid.
• Let the Trie tell you which paths are still worth following.

Here is how I would reason through it live:

Build the Trie.

• Insert every word. Shared prefixes become shared paths.
• If "oath" and "oats" are both in the list, the grid search explores o -> a -> t once, not twice.

DFS from every cell.

• Start a depth-first walk at each cell of the grid.
• As I move to a neighbor, I move down one level in the Trie in lockstep.
• The current grid letter must match a child in the current Trie node. If it does not, I stop immediately.
• This is the pruning that makes it fast: the Trie kills dead branches before I waste time on them.

When a Trie node has is_end true:

• I have spelled a complete word along this grid path.
• Add it to the result set.

Handle the "used cell" rule.

• Mark the current cell as visited before recursing, then unmark it when I back out.
• Standard backtracking.

Let me trace a tiny case. Grid:

o a a n
e t a e

Words: ["eat", "oath"]. Build the Trie, two paths from the root: one down e -> a -> t, one down o -> a -> t -> h.

Start DFS at cell (1,0), which holds e.

• Root has a child e, good, step into it.
• Neighbors of e: o above, t to the right.
• Trie node e has a child a, not o or t.
• Moving to o or t fails the Trie check and gets pruned. Dead end here.
• Correct, because "eo..." and "et..." are not prefixes of any word.

A quick sanity check on "eat":

• From e at (1,0), the right neighbor at (1,1) is t, and there is no a adjacent below this e.
• So this particular e cannot start "eat". The algorithm correctly moves on.
• The grid drawn here does not actually contain "eat" as a path, which is exactly the kind of chase the Trie saves you from.

Now start DFS at (0,0) = o.

• Root has child o. Step in.
• Neighbor a at (0,1)? Trie node o has child a, yes. Step to a.
• Neighbor t at (1,1)? Trie node a has child t, yes. Step to t.
• Neighbor h? None adjacent. So "oath" is not completable here either.
• Fine. The search was still cheap because every step was Trie-guided, and we never explored a single letter that was not on a live Trie path.

The magic:

• One grid traversal handled all words at once.
• The Trie pruned every path that could not lead to a real word.
• You pay cells * 4^L once, bounded by what the Trie actually contains, instead of words * cells * 4^L.

5Variations and gotchas#

Most Trie problems are the base skeleton plus one of these. Learn the twist, not a new structure.

Wildcard search.

• Some problems let a query contain . meaning "any one character."
• Exact walk breaks here. The fix: when you hit a ., recurse into all children at that node instead of a single one.
• This is the "Add and Search Word" pattern.
• It turns a linear walk into a branching search, but only on the . positions, so a query with two dots branches twice and the rest is still a straight walk.

Binary Trie for XOR.

• For "maximum XOR of two numbers in an array," insert each number as a 32-bit path (each bit is an edge, 0 or 1).
• To maximize XOR for a query number, at each bit greedily go down the opposite bit's child.
• Opposite bits XOR to 1, and a 1 in a higher bit beats anything below it.
• This is a Trie in disguise, and interviewers love it because most people do not see the tree hiding inside a bit problem.

Storing a value, not just a flag.

• Instead of is_end, store the full word, a frequency count, or an index.
• Useful for "replace words with roots," autocomplete ranking, or returning the matched string directly instead of reconstructing it from the path.

Array vs hash map for children.

• For lowercase English, a fixed array of size 26 is faster and simpler than a hash map.
• For unicode or mixed input, use a map.
• Say the trade-off out loud: the 26-array is cache-friendly and avoids hashing per step, but it wastes memory on sparse nodes. That one sentence signals you understand the memory cost.

Deletion.

• Rarely asked, often botched. You do not just flip is_end off.
• If the node has no children after unflagging, prune it upward.
• Stop pruning at any node that is another word's end or has other children.
• Delete "car" from a Trie that also holds "card" and you must keep the whole c -> a -> r path alive, only clearing r's end flag.

6Complexity#

Let L be the length of a word or prefix, N the number of words, and A the alphabet size (26 for lowercase English).

• Insert: O(L) time.
• Search / startsWith: O(L) time. Independent of how many words you stored. Query a prefix of length 3 against a million words and you still touch 3 nodes. This is the headline feature.
• Build the whole Trie: O(total characters across all words).
• Space: O(total characters) in the worst case, with a constant factor of A per node if you use fixed-size arrays. Shared prefixes save memory in practice, but the worst case has no sharing, so plan for it when the interviewer asks.
• Wildcard search: worst case O(A^L) when the query is all dots, because every position branches across all children. Usually far better, since real queries have few dots.

Compare to a hash set:

• Exact lookup is O(L) too.
• But a hash set cannot do prefix queries at all, and that is the whole reason you paid for the Trie.
• If the problem never asks a prefix question, the hash set wins on both space and simplicity.

7Mistakes that cost people the round#

• Forgetting the is_end flag. Insert "apple", then search("app") returns true because the path exists. Wrong. Without the end flag you cannot distinguish a word from a mere prefix. The single most common bug, and it passes the toy tests and dies on the real ones.
• Confusing search and startsWith. Almost identical code, differing by one is_end check. Mixing them up silently passes small tests and fails big ones, and it is a brutal bug to find when the clock is running.
• Reaching for a Trie when a hash set is enough. If there is only exact-match lookup and no prefix question, a Trie is over-engineering. Interviewers notice when you pick the heavier tool without reason, and it reads as pattern-matching instead of thinking.
• In Word Search II, searching per word instead of one combined grid DFS. This is the entire point of the problem. Per-word DFS is the answer they want you to improve on, so landing there and stopping is landing on the brute force they already expected.
• Forgetting to backtrack the visited marker on grid problems. You get words that reuse a cell, and the bug is maddening to spot under pressure because the structure looks right.
• Not pruning in wildcard search. Recursing into all children is right, but return early once you have confirmed a match or hit a dead node, otherwise you explore branches you already answered.
• Hand-waving the node structure. Say it clearly: "each node is a map of children plus an end flag." Interviewers want to hear you name the two fields before you write any method, because it proves you have the shape in your head and are not improvising.

8Your practice path (named problems by difficulty)#

Do them in this order. Each one adds exactly one new idea, so you are never learning two things at once.

Warm up (Easy to Medium):

• Implement Trie (Prefix Tree)
• Longest Common Prefix
• Index Pairs of a String

Core Medium (the ones that teach the pattern):

• Design Add and Search Words Data Structure (the wildcard . variation)
• Replace Words (store and return the shortest root)
• Map Sum Pairs (store values, sum over a prefix subtree)
• Search Suggestions System (autocomplete ranking)
• Maximum XOR of Two Numbers in an Array (the binary Trie trick)

Hard (where it all combines):

• Word Search II (Trie + grid DFS + backtracking, the worked example above)
• Concatenated Words
• Stream of Characters
• Palindrome Pairs
• Word Squares

If you only have time for three:

• Implement Trie, Add and Search Words, and Word Search II.
• That trio covers build, wildcard, and the DFS combo, which is the bulk of what gets asked.
• Spend an hour getting Implement Trie fully fluent before touching the rest, because every other problem assumes you can write that skeleton in your sleep.

9Where this shows up (which companies and rounds lean on it)#

Tries show up most in companies with search, autocomplete, or large text systems.

• Google asks prefix and autocomplete framing often.
• Amazon likes Word Search II and the design-a-dictionary variants.
• Microsoft and Uber reach for the wildcard version.
• Quant and systems-heavy shops pose the binary-Trie XOR problem to see if you can spot the hidden tree inside a bit problem.

Where it lands in the loop:

• The standard algorithms round, most of the time.
• Occasionally a design-flavored "build an autocomplete service" discussion, where the Trie is the storage layer under the hood.
• If you get that design prompt, name the Trie as the prefix index, then talk about sharding it by first letter. That is exactly the move they are listening for.

See a set of strings and repeated prefix questions, build the Trie before you write a line.

Want to see which of these problems a specific company actually asks? Check the company guides to map this pattern to the rooms you will be sitting in.