Implement Trie (Prefix Tree) (LC 208)

Pattern: Trie (Prefix Tree)
Difficulty: Medium
Key Concept: Each node holds links to 26 (or alphabet-sized) children and an isEnd flag; insert walks/creates edges; search/startsWith follow edges and check termination.

Problem Statement

Implement a Trie (PrefixTree) with:

• void insert(String word)
• boolean search(String word) — true iff the word was inserted
• boolean startsWith(String prefix) — true if some inserted word has this prefix

Input: Strings of lowercase English letters (typical LeetCode constraint).
Output: Boolean results per query.

---

1. Algorithm & Pseudocode

Brute force

1. Store all words in a HashSet<String>.
2. insert → add to set O(1) amortized.
3. search → set.contains(word) O(|word|) hash.
4. startsWith → iterate all stored words and check word.startsWith(prefix) — O(N × L) per query, N = number of words.

Pseudocode

words = hash set
prefixes = maybe not needed

insert(w): words.add(w)

search(w): return w in words

startsWith(p):
    for w in words:
        if w starts with p: return true
    return false

Optimal

1. Node with TrieNode[26] children (or Map<Character, TrieNode>) and boolean end.
2. insert: for each char c, cur = cur.children[c] or create; mark end at last char.
3. search: walk chars; fail if missing link; require end at end.
4. startsWith: same walk but do not require end.

Pseudocode

insert(word):
    cur = root
    for ch in word:
        idx = ch - 'a'
        if cur.children[idx] == null: cur.children[idx] = new Node
        cur = cur.children[idx]
    cur.end = true

search(word):
    cur = walk(word); return cur != null && cur.end

startsWith(prefix):
    cur = walk(prefix); return cur != null

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Why not only a hash set: Prefix queries need shared structure; trie shares common prefixes in memory and answers startsWith in O(m) where m = prefix length.
• Array vs map for children: Fixed alphabet a-z → array of 26 is fast and cache-friendly; HashMap helps sparse/Unicode alphabets.
• end flag: Without it, inserting "app" would make search("ap") ambiguous if "ap" was never inserted but is a prefix of "app".

---

3. The Dry Run

Insert "app", "apple", then startsWith("app"), search("app").

After inserts (only showing used edges; * = end)

root
 └─a
   └─p
     └─p*
       └─l
         └─e*

Operation	Walk	Result
insert app	a→p→p, mark end at 2nd p	—
insert apple	extend l→e, mark end	—
startsWith app	a,p,p all exist	true
search app	ends at p with end=true	true
search ap	ends at first p? Actually after “ap” we’re at node after a,p — no end unless inserted	false

ASCII (compact)

        (root)
          |
          a
          |
          p
          |
          p*  ← "app" ends here
          |
          l
          |
          e*  ← "apple"

---

4. Java Solution

Brute Force

import java.util.*;

class TrieBrute {
    private final Set<String> words = new HashSet<>();

    public TrieBrute() {}

    // insert O(L), search O(L), startsWith O(N * L) per query
    public void insert(String word) {
        words.add(word);
    }

    public boolean search(String word) {
        return words.contains(word);
    }

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

Optimal

class Trie {
    private static class Node {
        Node[] next = new Node[26];
        boolean end;
    }

    private final Node root = new Node();

    public Trie() {}

    // insert: O(L), Space: O(total chars stored) shared prefixes
    public void insert(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (cur.next[idx] == null) cur.next[idx] = new Node();
            cur = cur.next[idx];
        }
        cur.end = true;
    }

    public boolean search(String word) {
        Node n = walk(word);
        return n != null && n.end;
    }

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

    private Node walk(String s) {
        Node cur = root;
        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            if (cur.next[idx] == null) return null;
            cur = cur.next[idx];
        }
        return cur;
    }
}

---

5. The “Java vs. Others” Edge

• Node[] next = new Node[26] avoids autoboxing vs Map<Character, TrieNode>.
• For Unicode, use Map or compressed trie (advanced).
• LeetCode expects class name Trie; constructor Trie().

---

6. Complexity Summary

Approach	insert	search	startsWith	Space
Brute HashSet	O(L) avg	O(L) avg	O(N·L)	O(N·L) stored strings
Trie	O(L)	O(L)	O(P) prefix len	O(ALPHABET × nodes) shared