61.Implement Trie (Prefix Tree)

MediumBlind 75Tries · 1/3

Problem

A trie (prefix tree) stores a set of strings so that prefix questions can be answered quickly. Implement the Trie class:

Trie() initializes an empty trie.
void insert(String word) inserts word.
boolean search(String word) returns true if word was inserted before (as a whole word).
boolean startsWith(String prefix) returns true if any inserted word starts with prefix.

Examples

Input:  ["Trie","insert","search","search","startsWith","insert","search"]
        [[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
Output: [null,null,true,false,true,null,true]
Explanation: "app" is only a prefix of "apple" until "app" itself is inserted.

Input:  ["Trie","insert","insert","startsWith","search","startsWith"]
        [[],["car"],["cat"],["ca"],["ca"],["cb"]]
Output: [null,null,null,true,false,false]
Explanation: "ca" prefixes both words but was never inserted; nothing starts with "cb".

Constraints

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

💡 Key Insight

Words that share a prefix should share storage. A trie stores one node per distinct prefix: walking down L edges answers "is this a prefix?" in O(L), independent of how many words are stored. An isEnd flag on a node distinguishes "a word ends here" from "this is merely a prefix of a longer word".

Brute Force (List of Words)

TimeO(1) amortized for insert; O(n · L) for search and startsWithSpaceO(total characters inserted)

Intuition

Keep every inserted word in a list. search checks for an equal string, startsWith checks every word with String.startsWith. It is correct but every query scans all n stored words.

Algorithm

insert: append word to words.
search: return true if any stored word equals(word).
startsWith: return true if any stored word startsWith(prefix).

Visualization

words = ["apple", "app"]

startsWith("ap"):
  "apple".startsWith("ap") -> true  -> return true
search("appl"):
  "apple".equals("appl") -> false
  "app".equals("appl")   -> false   -> return false

Code

java

import java.util.ArrayList;
import java.util.List;

class Trie {
    private final List<String> words = new ArrayList<>();

    public Trie() {
    }

    public void insert(String word) {
        words.add(word);
    }

    public boolean search(String word) {
        for (String w : words) {
            if (w.equals(word)) {
                return true;
            }
        }
        return false;
    }

    public boolean startsWith(String prefix) {
        for (String w : words) {
            if (w.startsWith(prefix)) {
                return true;
            }
        }
        return false;
    }
}

Complexity

Time: O(1) amortized for insert; O(n · L) for search and startsWith — up to n stored words, each comparison costs up to L characters.
Space: O(total characters inserted) — every word stored separately, with no prefix sharing.

Trie with HashMap Children

TimeO(L) per operationSpaceO(total characters inserted) in the worst case

Intuition

Build a tree where each edge is a character. The path from the root to a node spells a prefix. Each node keeps a HashMap<Character, Node> of children and a boolean isEnd. Inserting walks the path, creating missing nodes; searching walks the path and fails as soon as a character edge is missing.

Algorithm

insert: start at root; for each char c, computeIfAbsent(c, new Node) and move to it. Mark the final node isEnd = true.
Helper walk(s): follow each char from root; return null if an edge is missing, otherwise the final node.
search(word): node = walk(word); return node != null && node.isEnd.
startsWith(prefix): return walk(prefix) != null.

Visualization

After inserting "app", "apple" and "bat" (* marks isEnd):

flowchart TD
    R["root"] -->|"a"| A["a"]
    R -->|"b"| B["b"]
    A -->|"p"| P1["ap"]
    P1 -->|"p"| P2["app *"]
    P2 -->|"l"| L["appl"]
    L -->|"e"| E["apple *"]
    B -->|"a"| BA["ba"]
    BA -->|"t"| BT["bat *"]

search("appl") reaches node appl, which exists but has isEnd = false → false. startsWith("appl") only needs the node to exist → true.

Code

java

import java.util.HashMap;
import java.util.Map;

class Trie {
    private static class Node {
        Map<Character, Node> children = new HashMap<>();
        boolean isEnd;
    }

    private final Node root = new Node();

    public Trie() {
    }

    public void insert(String word) {
        Node node = root;
        for (char c : word.toCharArray()) {
            node = node.children.computeIfAbsent(c, k -> new Node()); // create edge if missing
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Node node = walk(word);
        return node != null && node.isEnd; // must end exactly at a word
    }

    public boolean startsWith(String prefix) {
        return walk(prefix) != null; // any path is enough
    }

    // Follows s from the root; returns null if some character edge is missing.
    private Node walk(String s) {
        Node node = root;
        for (char c : s.toCharArray()) {
            node = node.children.get(c);
            if (node == null) {
                return null;
            }
        }
        return node;
    }
}

Complexity

Time: O(L) per operation — one map lookup per character.
Space: O(total characters inserted) in the worst case — shared prefixes are stored once; each node carries HashMap overhead.

Trie with Array ChildrenOptimal

TimeO(L) per operationSpaceO(N · 26) where N is the number of trie nodes (at most the total characters inserted).

Intuition

The alphabet is fixed at 26 lowercase letters, so a Node[26] array indexed by c - 'a' replaces the HashMap. Lookups become direct array indexing — no hashing, no boxing of Character — which is the standard, fastest trie for this problem.

Algorithm

Each TrieNode holds TrieNode[] children = new TrieNode[26] and boolean isEnd.
insert: for each char, compute i = c - 'a'; if children[i] is null, create it; move down. Set isEnd at the end.
walk(s) follows indices and returns null on the first missing child.
search = walk non-null and isEnd; startsWith = walk non-null.

Dry Run

sequenceDiagram
    participant C as Caller
    participant T as Trie
    C->>T: insert('apple')
    Note over T: creates a-p-p-l-e, marks e as end
    C->>T: search('apple')
    T-->>C: true (node e has isEnd)
    C->>T: search('app')
    T-->>C: false (second p exists, isEnd false)
    C->>T: startsWith('app')
    T-->>C: true (path exists)
    C->>T: insert('app')
    Note over T: no new nodes, marks second p as end
    C->>T: search('app')
    T-->>C: true

Code

java

class Trie {
    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd;
    }

    private final TrieNode root = new TrieNode();

    public Trie() {
    }

    public void insert(String word) {
        TrieNode node = root;
        for (int k = 0; k < word.length(); k++) {
            int i = word.charAt(k) - 'a';
            if (node.children[i] == null) {
                node.children[i] = new TrieNode();
            }
            node = node.children[i];
        }
        node.isEnd = true; // a complete word ends here
    }

    public boolean search(String word) {
        TrieNode node = walk(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }

    private TrieNode walk(String s) {
        TrieNode node = root;
        for (int k = 0; k < s.length(); k++) {
            node = node.children[s.charAt(k) - 'a'];
            if (node == null) {
                return null; // path breaks: neither word nor prefix
            }
        }
        return node;
    }
}

Complexity

Time: O(L) per operation — one array access per character.
Space: O(N · 26) where N is the number of trie nodes (at most the total characters inserted).

Complexity Comparison

Approach	Time (insert / search / startsWith)	Space
List of Words	O(1) / O(n·L) / O(n·L)	O(total chars)
Trie (HashMap)	O(L) / O(L) / O(L)	O(total chars)
Trie (Array)	O(L) / O(L) / O(L)	O(nodes · 26)

Common Pitfalls

Returning true from search just because the path exists — search("app") after inserting only "apple" must be false; check isEnd.
Forgetting to set isEnd when inserting a word that is a prefix of an existing one (no new nodes are created, but the flag must still be set).
Using c directly as an index instead of c - 'a' (index out of bounds).
Sharing one static root across instances — LeetCode creates a fresh Trie per test, so keep root an instance field.