Trie (Prefix Tree): Complete Guide with Examples

A trie (pronounced like the word try) stores a set of strings as a shared tree of prefixes. Each node holds one character, and the path from the root to a node spells out a prefix. Words that share a prefix share the same nodes along that path, so the structure never stores the same prefix twice. This is what makes prefix lookups cheap: finding every word that starts with “inter” only requires walking the path for “inter” instead of scanning the whole set.

Definition: a trie is a tree where each node carries one character and a flag that marks whether a complete word ends at that node. Descending one level commits to one more character, so the depth of a node equals the length of the prefix it represents.

The structure earns its keep when the operation is about prefixes. A hash set answers “is this exact word stored” in

Real-World Analogy

Think of a hardcover dictionary with thumb-index tabs. The tab for P opens a section that holds every word starting with p. Inside that section the pages are ordered so that all the pa words come before all the pe words. You never scan the whole dictionary to find a word. You jump to the tab, then to the right page range, and each step narrows the search by one letter.

A trie works the same way. The root is the shelf. Each node is one letter position. Descending one level commits to one more character, and every word below a node shares the prefix that node represents. Two words diverge only at the first character where they differ, exactly like two dictionary entries split onto different pages at their first different letter.

Visual Explanation

Here is a trie storing the words “app”, “apple”, “apply”, and “apt”:

    flowchart TD
    ROOT((root))
    A((a))
    P1((p))
    P2((p))
    T((t*))
    L1((l))
    E((e*))
    Y((y*))
    P3((p*))

    ROOT --> A
    A --> P1
    P1 --> P2
    P1 --> T
    P2 --> P3
    P2 --> L1
    L1 --> E
    L1 --> Y

    style T fill:#c8e6c9
    style E fill:#c8e6c9
    style Y fill:#c8e6c9
    style P3 fill:#c8e6c9
  

The green nodes carry the end marker. Notice what is shared: “app”, “apple”, and “apply” all ride the same a-p-p path and only branch at the fourth character. The trie stores the shared prefix once, so a lookup for any of these words touches at most five nodes even though four words are stored. Searching for “apt” costs the same as searching for “apple” even though the words only share the letter a.

Inserting a word is a descent. Walk the characters, create any node that does not exist yet, and mark the final node as a word end.

    flowchart LR
    subgraph Step1["Step 1: insert 'a'"]
        R1((root)) --> A1((a))
    end

    subgraph Step2["Step 2: insert 'p'"]
        R2((root)) --> A2((a)) --> P2((p))
    end

    subgraph Step3["Steps 3 to 5: finish the word"]
        R3((root)) --> A3((a)) --> P3((p)) --> P4((p)) --> L3((l)) --> E3((e*))
    end

    style E3 fill:#c8e6c9
  

Searching follows the same path but fails the moment a character is missing. Prefix search is identical to search except it ignores the end marker. A wildcard search, where some positions may match any character, turns the descent into a depth-first search: at a wildcard position you try every child branch and stop at the first branch that completes the match.

When to Use This Pattern

Use a trie when the problem has these characteristics.

• You need to answer prefix queries, like “which stored words start with this string”, against a fixed set of words. Autocomplete and type-ahead problems are the canonical case.
• You are checking membership for many strings and the words share long prefixes, so the shared structure saves real memory. This is typical for dictionaries, DNA sequences, and IP routing tables.
• You must enumerate all words that share a prefix, or find the shortest unique prefix of each word. Both reduce to one descent plus a walk of the subtree below a node.
• The problem asks you to build words one character at a time, like finding the longest word that can be built from other stored words. The trie encodes exactly the “is every prefix stored” check that these problems need.
• You expect many more lookup operations than inserts. The build cost pays off when lookups dominate.

Skip the trie when the problem only needs exact membership checks. A hash set is simpler, faster on average, and easier to explain. Reach for the trie when the word “prefix” actually appears in the requirements.

Complexity Analysis

Every operation walks at most M characters, where M is the length of the word or prefix. The number of stored words never enters the cost of a single operation.

The time bound falls out of the structure itself. Each character of the input matches exactly one node level, so the walk is one step per character. There is no search, no retry, and no dependence on how many words sit in other branches.

The space story is where the trie trades memory for speed. In the worst case, where no two words share a prefix, storing N words of average length M costs

Common Mistakes

Forgetting the end-of-word marker. If no node records whether a word ends there, search and prefix search become the same operation. Storing “apple” and then searching for “app” returns true, because the path exists even though “app” was never inserted. The marker is the only thing that distinguishes a stored word from a stored prefix. Catch it during practice by testing a word that is a strict prefix of another word: “app” must fail after only “apple” is inserted.

Calling search when the problem asks startsWith, or the reverse. The two methods look nearly identical and share the same traversal. The difference is exactly one line, the check of the end marker. Interviewers use this pairing to see whether you understand what the marker means. Read the problem statement for “is a word” versus “starts with” and match the method to that phrasing before you write anything.

Deleting without pruning, or pruning shared nodes. Removing a word has two parts: unset the end marker and delete nodes that no longer belong to any word. The second part must stop at any node that is itself a word end or still has children, because other words may live below it. A delete that removes shared nodes silently breaks the words that pass through them. Trace the delete on two words that share a long prefix before you write the recursion.

Choosing the wrong children structure. A node’s children can be a hash map or a fixed array with one slot per possible character. The array is faster to look up but allocates every slot up front, so it only makes sense when the alphabet is small and known, like 26 lowercase letters. A hash map wastes nothing but pays a little more per lookup. Match the choice to the alphabet stated in the problem and be ready to justify it, because interviewers often ask why you picked one over the other.

Related Patterns

• Hash Table . For exact word membership a hash set is simpler and faster on average. The trie earns its extra structure only when prefix queries matter, so the two pages are two halves of the same “is this string here” question.
• Backtracking . Wildcard searches and Word Search II drive the trie with depth-first search and backtracking over branches. The backtracking page covers the general explore, undo, retry loop that these searches use.
• String Manipulation . Prefix-heavy string problems such as longest common prefix can be solved with sorting, but a trie answers the same questions with a different tradeoff. Compare the two approaches when a problem involves both strings and prefixes.

Next Steps

Once the concept is clear, the next step is making the code automatic. Check out the code templates for memorizable implementations in 6 languages, then work through the practice problems to apply the pattern to real interview questions.