Implement Trie (Prefix Tree)

Implement Trie (Prefix Tree) easy

Description

Implement a Trie class with:

insert(word) — add word to the trie.
search(word) — return true if word was inserted (exact match).
startsWith(prefix) — return true if any inserted word starts with prefix.

Examples

> trie.insert("apple")
  trie.search("apple")     -> true
  trie.search("app")       -> false   # "app" was never inserted as a word
  trie.startsWith("app")   -> true    # but it IS a prefix of "apple"
  trie.insert("app")
  trie.search("app")       -> true    # now it is a word

Constraints

1 <= word.length, prefix.length <= 2000
lowercase English letters only.
up to 3 × 10^4 calls total.

Try it

Try it — insert words, then search or check a prefix

Words in the trie: apple

Intuition

Every operation is a walk down character-by-character. insert creates missing nodes; search and startsWith follow existing ones. The only difference between the two queries is whether you check the isEnd flag at the final node — that flag is what separates “a complete word ends here” from “this is merely a prefix.”

Code

⚠️

The #1 bug: returning true from search just because the path exists. Always check the end flag. search("app") after inserting only "apple" must be false — the path to p-p exists, but no word ends there. startsWith is the one that ignores the flag.

Analysis

Time: O(L) per operation, where L is the word/prefix length — independent of how many words are stored.
Space: O(total characters inserted) with map children; O(N · L · 26) worst case with array children.

Same skin

Every other problem in this chapter starts from this class.
Add & Search Word — same trie, but search becomes a DFS to handle . wildcards.
Design HashMap / HashSet — the hash-based analog when you only need exact lookup, not prefixes.

Overview Add & Search Word