#208 Implement Trie (Prefix Tree)

frequently reported atApple Oracle Microsoft Amazon Google Meta

the problem

In plain words

Build a class Trie with insert(word), search(word) (is this exact word stored?) and startsWith(prefix) (is any stored word starting with prefix?).

in insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")

out null, true, false, true, null, true

"app" is only a prefix until it is inserted itself.

1 ≤ word.length, prefix.length ≤ 2000
Lowercase English letters only
At most 3·10⁴ calls in total

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTrie (prefix tree)

Each node stands for a prefix. A path that exists means the prefix exists; an end-of-word flag at the last node means the whole word exists.

solutions

From brute force to optimal

Store the words in a set; for startsWith, scan every word.

insert → set.add(word).
search → set.contains(word).
startsWith → loop over all words and test w.startsWith(prefix).

timeO(L) insert/search, O(N·L) startsWith

Hashing reads the word once; a prefix has no bucket, so every word must be checked.

spaceO(S)

The words themselves, S = total letters.

javaclass Trie (HashSet version)java.util.*

1class SetTrie {2    private final Set<String> words = new HashSet<>();3 4    public void insert(String word) {5        words.add(word);6    }7 8    public boolean search(String word) {9        return words.contains(word);10    }11 12    public boolean startsWith(String prefix) {13        for (String w : words) {          // scans every stored word14            if (w.startsWith(prefix)) return true;15        }16        return false;17    }18}

Walk one node per letter; create missing nodes on insert; check the end flag on search.

Node = Node[26] children + boolean isEnd.
insert: from the root, for each letter create the child if missing and step into it; set isEnd at the end.
walk(s): follow letters, return null if a child is missing.
search = walk(word) != null && isEnd; startsWith = walk(prefix) != null.

timeO(L) per operation

One array lookup per letter, independent of how many words are stored.

spaceO(S·26)

Up to one node per inserted letter, each holding 26 references.

javajava.util.*

1class Trie {2    private static class Node {3        Node[] children = new Node[26]; // one slot per letter 'a'..'z'4        boolean isEnd;                  // true if a word ends exactly here5    }6 7    private final Node root = new Node();8 9    public void insert(String word) {10        Node cur = root;11        for (char ch : word.toCharArray()) {12            int i = ch - 'a';13            if (cur.children[i] == null) cur.children[i] = new Node();14            cur = cur.children[i];15        }16        cur.isEnd = true;17    }18 19    public boolean search(String word) {20        Node node = walk(word);21        return node != null && node.isEnd;22    }23 24    public boolean startsWith(String prefix) {25        return walk(prefix) != null;26    }27 28    /** Follows s letter by letter; null as soon as a letter is missing. */29    private Node walk(String s) {30        Node cur = root;31        for (char ch : s.toCharArray()) {32            cur = cur.children[ch - 'a'];33            if (cur == null) return null;34        }35        return cur;36    }37}

sim

Dry run

loading simulation…

javajava.util.*

1class Trie {2    private static class Node {3        Node[] children = new Node[26]; // one slot per letter 'a'..'z'4        boolean isEnd;                  // true if a word ends exactly here5    }6 7    private final Node root = new Node();8 9    public void insert(String word) {10        Node cur = root;11        for (char ch : word.toCharArray()) {12            int i = ch - 'a';13            if (cur.children[i] == null) cur.children[i] = new Node();14            cur = cur.children[i];15        }16        cur.isEnd = true;17    }18 19    public boolean search(String word) {20        Node node = walk(word);21        return node != null && node.isEnd;22    }23 24    public boolean startsWith(String prefix) {25        return walk(prefix) != null;26    }27 28    /** Follows s letter by letter; null as soon as a letter is missing. */29    private Node walk(String s) {30        Node cur = root;31        for (char ch : s.toCharArray()) {32            cur = cur.children[ch - 'a'];33            if (cur == null) return null;34        }35        return cur;36    }37}

Same algorithm, but each node maps only the letters it actually has.

children = new HashMap<Character, Node>().
insert uses computeIfAbsent; walk uses get.

timeO(L) average per operation

One hash lookup per letter.

spaceO(S)

Only existing edges are stored (but each map entry is a heavier object).

javajava.util.*

1class MapTrie {2    private static class Node {3        Map<Character, Node> children = new HashMap<>(); // only letters that exist4        boolean isEnd;5    }6 7    private final Node root = new Node();8 9    public void insert(String word) {10        Node cur = root;11        for (char ch : word.toCharArray()) {12            cur = cur.children.computeIfAbsent(ch, k -> new Node());13        }14        cur.isEnd = true;15    }16 17    public boolean search(String word) {18        Node node = walk(word);19        return node != null && node.isEnd;20    }21 22    public boolean startsWith(String prefix) {23        return walk(prefix) != null;24    }25 26    private Node walk(String s) {27        Node cur = root;28        for (char ch : s.toCharArray()) {29            cur = cur.children.get(ch);30            if (cur == null) return null;31        }32        return cur;33    }34}

in the room

How to say it in the interview

talk track

Clarify the alphabet (lowercase a–z?) — it decides array vs map.
Draw "apple" and "app" sharing a path, and point at why isEnd is needed.
Write walk() once and reuse it — interviewers notice the lack of duplication.
Close with complexity: O(L) per call, O(S·26) memory, and the map alternative.

traps

search returning true for a prefix (missing the isEnd check).
Allocating new Node[26] for the root but forgetting to create child nodes before stepping into them (NullPointerException).

what they ask next

Follow-ups

Implement Trie II (LC 1804): count words equal to / starting with, and erase?

Add pass and end counters to each node — see the counting trie in this chapter. All operations stay O(L).

How would you save memory?

Use a map per node, or a radix (compressed) trie where chains of single-child nodes become one edge labelled with a string.

before you submit

Edge cases to test

search for a prefix of a stored word ("app" when only "apple" is stored) → false.
startsWith with a whole stored word → true: a word is its own prefix.
Inserting the same word twice → nothing changes; it is still found.
A 2000-letter word → 2000 nodes on one path; a loop handles it without recursion.

practise next