Free lesson · DSA Mastery - Interview Prep, End to End

Implement Trie (Prefix Tree)

Medium8 min readdsatries

Implement Trie (Prefix Tree)

Implement Trie (Prefix Tree) builds the data structure itself: a Trie class supporting insert, search (exact word), and startsWith (prefix test). It turns the two primitives from the introduction into working code and establishes the node representation, the insert-creates-missing-children pattern, and the crucial isEnd distinction between a complete word and a mere prefix - the foundation every subsequent problem in the section relies on. We present the array-backed implementation (canonical), with the hashmap-child variant noted for large alphabets.

The insight: all three operations are the same walk down the tree, one edge per character, differing only in what happens at a missing child and what they check at the end. Insert creates missing children and flags the final node as a word-end. Search and startsWith both stop early if a child is missing; they diverge only at the finish - search requires the isEnd flag, while startsWith is satisfied merely by reaching the node. Recognizing that one traversal underlies all three keeps the implementation tight.

The Problem

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // true
trie.search("app");     // false  (inserted "apple", not "app")
trie.startsWith("app"); // true   ("apple" has prefix "app")
trie.insert("app");
trie.search("app");     // true

Constraints:

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters.
• At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.

Approaches Overview

Both store the trie as nodes with child pointers and an isEnd flag, and both run every operation in O(L) where L is the string length. The 26-slot array gives O(1) child access with a fixed constant, ideal for lowercase-English; the hashmap variant trades a small constant for flexibility when the alphabet is large or unknown. The array version is the canonical answer for this problem's lowercase constraint.

Approach 1: Array-Backed Children - Canonical

The Idea

Each node holds TrieNode[26] children and a boolean isEnd. insert: walk from the root; for each character, create the child if absent, then descend; mark isEnd at the final node. search: walk the characters; if any child is missing, return false; at the end return the node's isEnd. startsWith: identical walk, but return true simply for reaching the end (ignore isEnd). Factor the shared walk into a helper that returns the node reached (or null).

Logic Flowchart

graph TD
    A["operation on string s"] --> B["node = root"]
    B --> C["for each char ch in s"]
    C --> D{"child for ch exists?"}
    D -->|"No, insert"| E["create child"]
    D -->|"No, search/startsWith"| F["return null / false"]
    D -->|Yes| G["node = child"]
    E --> G
    G --> C
    C --> H{"which operation?"}
    H -->|insert| I["node.isEnd = true"]
    H -->|search| J["return node.isEnd"]
    H -->|startsWith| K["return true (reached node)"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style G fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style H fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style J fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style K fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the three trie operations sharing one walk. Insert creates missing children and flags the end as a word; search returns the end flag on arrival; starts-with returns true simply for reaching the final node.

Code

class Trie {
    private final Trie[] children = new Trie[26];
    private boolean isEnd = false;

    public Trie() {}

    public void insert(String word) {
        Trie node = this;
        for (char ch : word.toCharArray()) {
            int i = ch - 'a';
            if (node.children[i] == null) node.children[i] = new Trie();  // create if absent
            node = node.children[i];
        }
        node.isEnd = true;                       // mark end of a complete word
    }

    public boolean search(String word) {
        Trie node = walk(word);
        return node != null && node.isEnd;        // must be a flagged word-end
    }

    public boolean startsWith(String prefix) {
        return walk(prefix) != null;              // reaching the node is enough
    }

    // shared walk: returns the node for the string, or null if a child is missing
    private Trie walk(String s) {
        Trie node = this;
        for (char ch : s.toCharArray()) {
            int i = ch - 'a';
            if (node.children[i] == null) return null;
            node = node.children[i];
        }
        return node;
    }
}

// Usage:
// insert("apple"); search("apple") -> true; search("app") -> false; startsWith("app") -> true

This Java code implements the trie with a 26-slot child array and an isEnd flag. Insert creates missing children and flags the end; a shared walk helper returns the node reached, which search checks for isEnd and starts-with checks only for existence.

Step-by-Step Walkthrough

A frame-by-frame trace on the example sequence:

graph LR
    F0["insert('apple'): create a-p-p-l-e path; isEnd at final e"]
    F1["search('apple'): walk reaches e, isEnd=true → true"]
    F2["search('app'): walk reaches 2nd p, isEnd=false → false"]
    F3["startsWith('app'): walk reaches 2nd p (exists) → true"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough runs the operations. Inserting apple creates its path with the end flagged. Searching apple succeeds; searching app fails because no word ends there; starts-with app succeeds because the path exists.

Result: true, false, true, then true after inserting "app".

Complexity

Time: O(L) per operation. Space: O(total characters inserted) for the nodes.

Approach 2: HashMap Children - Large/Unknown Alphabet

The Idea

Replace the fixed Trie[26] with a Map<Character, Trie>. The logic is identical - create missing children on insert, walk on search/startsWith - but children are looked up by character key instead of array index. This avoids wasting 26 slots per node when the alphabet is large (Unicode) or sparse, at the cost of hashing overhead per step.

Complexity

Time: O(L) per operation (expected, with O(1) map access). Space: O(total characters), with less waste on sparse alphabets.

Complexity Comparison

Both are O(L) per operation - the defining trie cost, independent of how many words are stored. The array version is fastest for the constrained lowercase alphabet here; the hashmap version generalizes to arbitrary characters and saves space on sparse data. The shared insight is that all three operations are one character-by-character walk.

Variations & Follow-ups

Why do search and startsWith differ only at the final step?

Both perform the identical walk: descend one child per character, failing immediately if a child is missing. The only difference is the success condition at the end of the string. search asks "is this an inserted word?" - which requires the final node's isEnd flag to be true, because reaching a node only proves the characters form a prefix of something, not a complete word. startsWith asks "is this a prefix of any inserted word?" - for which simply reaching the final node suffices, since the node's existence means some word passed through it. Sharing the walk and branching only at the end keeps the code minimal and makes the prefix-vs-word distinction explicit.

Why is the isEnd flag essential, and what breaks without it?

isEnd is the only thing distinguishing a stored word from an incidental prefix. Inserting apple creates nodes for a, ap, app, appl, apple, but only apple is a real word - the others are just prefixes along the way. Without isEnd, search("app") would walk to the existing app node and wrongly return true, even though app was never inserted. The flag marks exactly which of the many path-nodes correspond to complete insertions. This is the most common trie bug: conflating "this prefix exists in the tree" with "this word was inserted."

Why is every operation O(L) regardless of how many words the trie holds?

Each operation walks at most L edges - one per character of the input string - and does O(1) work per edge (an array index or map lookup, plus possibly creating a node). The number of other words in the trie never enters the cost, because the walk only follows the single path dictated by the input's characters; it never examines sibling branches or unrelated subtrees. This is the trie's signature property and why it scales: adding a million more words doesn't slow down a lookup of a length-L string. Contrast a list scan, which is O(n·L).

When should you choose a trie over a hash set for word storage?

If the only operation is whole-word membership (insert and exact search), a hash set is simpler, uses less memory, and is just as fast asymptotically (O(L) to hash the word). Choose a trie when you need prefix operations a hash set can't do: startsWith, autocomplete (list all words with a prefix), counting words with a prefix, or longest-common-prefix queries. The presence of startsWith in this very problem is the signal - it's trivial for a trie (one walk) and O(n·L) for a hash set (scan everything). Prefix capability is the deciding factor.

What about edge cases?

• Empty string: Walking zero characters lands on the root; isEnd on the root would mean the empty string was inserted (rare but consistent).
• Searching before any insert: The root has no children; every search/startsWith returns false.
• Word that is a prefix of another (Example 1, "app" within "apple"): Handled by isEnd - app is a word only after it's explicitly inserted.
• Repeated insert of the same word: Idempotent; re-walks the existing path and re-sets isEnd.

Common Interview Pitfalls

• Omitting isEnd. Then every prefix falsely reads as a word; search("app") wrongly succeeds.
• Reusing search logic for startsWith. startsWith must not check isEnd - reaching the node is enough.
• Forgetting to create missing children on insert. Insert must build the path; only search/startsWith bail on a missing child.
• Index errors with ch - 'a'. Ensure the alphabet assumption holds, or use a map for safety.

Why This Topic Matters

Implement Trie is the foundation for the entire section: insert, search, and startsWith are the primitives every later problem composes. It cements the node representation (child array plus isEnd), the create-missing-children insert pattern, and - most importantly - the prefix-versus-word distinction encoded by isEnd. Internalize these and the harder problems become recombinations of this one walk.

The next topic, Design Add and Search Words Data Structure, extends search with a wildcard: the dot character . matches any single letter, so searching c.t should match cat, cot, and cut. A literal character still follows a single edge, but a . forces branching into all present children, turning the linear search walk into a small recursive (DFS) exploration of the trie. It's the first problem where the trie search becomes a backtracking traversal rather than a straight-line walk - the gateway to the harder pattern-matching problems later in the section.

Back to DSA Mastery - Interview Prep, End to End