Tries · LC #208

Implement Trie

Implement a trie (prefix tree) supporting insert, exact-match search, and prefix search in O(L) time per operation where L is the word length.

mediumLC #208AMZ★★★GOO★★META★MSFT★★AAPL★

Mark as done

Confidence

Ask GPT Practice on LeetCodePractice

Statement

Problem & Approach

Problem statement, sample I/O, and key reasoning.

Implement a Trie with `insert(word)`, `search(word)` (returns true only on exact match), and `startsWith(prefix)` (returns true if any inserted word begins with the prefix).

Sample I/O

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple")   → true
trie.search("app")     → false
trie.startsWith("app") → true
trie.insert("app");
trie.search("app")     → true

Intuition

How to Think About It

Intuition

A trie stores characters at each node rather than whole strings, so all words sharing a prefix share the same node path - enabling O(L) insert/search instead of O(N·L) brute-force scan.

Core Concept

Each TrieNode holds 26 child pointers (one per lowercase letter) and a boolean `isEnd` flag. Insert walks character by character, creating nodes on demand, then sets `isEnd = true` on the last node. Search walks the same path and checks `isEnd`; startsWith walks without checking `isEnd`.

When to use

Autocomplete, spell-check, IP routing tables, dictionary word lookup, any scenario needing fast prefix queries over a set of strings.

When NOT to use

When the alphabet is very large (e.g., Unicode) - a HashMap-based trie or a compressed (Patricia) trie is more memory-efficient. Also avoid when simple hash-set membership suffices and prefix queries are not needed.

Key Insights

What to Know Cold

The `isEnd` flag distinguishes "apple" from "app" - without it, search cannot differentiate prefix from full word.
A Map<char, TrieNode> is more memory-efficient than a fixed 26-slot array when the working alphabet is sparse.
startsWith reuses the same traversal helper as search, just skips the `isEnd` check.
Deletion requires either lazy removal (clear `isEnd`) or reference-counting to prune dead nodes.
Trie depth equals the length of the longest inserted word - not the number of words.

1 example

Worked Examples

Basic insert + search + startsWith

Insert "apple", query exact match and prefix

Walk trie on insert (create nodes), walk on search (check isEnd), walk on startsWith (no isEnd check).

const trie = new Trie();
trie.insert("apple");
trie.search("apple");    // true  - isEnd set at 'e'
trie.search("app");      // false - isEnd NOT set at 'p'
trie.startsWith("app");  // true  - path exists through 'a','p','p'
trie.insert("app");
trie.search("app");      // true  - isEnd now set at second 'p'

Demonstrates the critical role of isEnd: prefix path existence alone does not confirm a stored word.