CMD Guide
Home › DSA

Trie

Step 14 in the DSA path · 1 concepts · 8 problems

0 / 9 complete

📘 Learn Trie from zero

A Trie (prefix tree) stores a set of strings as a tree of characters: every path from the root spells a prefix, and words that share a prefix share nodes. Each node holds up to 26 child pointers (one per lowercase letter) plus an isEnd flag marking where a complete word terminates. Insert, search, and startsWith all run in O(L) time where L is the word length, independent of how many words are stored. Trigger to use it: reach for a Trie whenever the problem revolves around prefixes — autocomplete / search suggestions, "does any stored word start with X", wildcard word matching, or repeatedly querying many words against one shared dictionary. We trace the canonical Implement Trie (Prefix Tree): insert "app", then insert "apple", then run several queries.

✨ Added by the guide to build intuition — not from the source course.

🏗️ Visual walkthrough — trace it step by step

Step 1 — Empty trie
root  (isEnd=false)
children: { }

We start with a single root node representing the empty prefix; it is never a word itself. Every insert and query walks down from root, following or creating one child per character. The root is a fixed anchor that all letter-paths branch from, so it is safe to share across all operations.

Step 2 — insert("app"): char 'a'
insert "app"   i=0  c='a'

root
 └─ a        <-- NEW node created
        ^ cursor

From root we look up child 'a'. It is missing, so we create the node and move the cursor into it. Creating-on-miss is safe: the prefix a now exists for any future word that shares it, and we have not yet flagged any word as ending — so no false word is introduced.

Step 3 — insert("app"): 'p','p' + mark end
insert "app"   i=1 'p', i=2 'p'

root
 └─ a
     └─ p
         └─ p  [END]   <-- isEnd=true

path spelled: a → p → p

We create child 'p' under a, then another 'p' under that, advancing the cursor each time. After the final character we set isEnd=true on the last node. The [END] flag (not the node's existence) is what makes "app" a real stored word, which is why search must check it later.

Step 4 — insert("apple"): reuse a→p→p
insert "apple"  i=0 'a', i=1 'p', i=2 'p'

root
 └─ a          (exists → follow)
     └─ p      (exists → follow)
         └─ p [END]   <-- cursor here, NOT recreated

shared prefix "app" reused, no new nodes

For the first three characters of "apple", each child already exists, so we follow them instead of creating. This is the core Trie win: "app" and "apple" share their common prefix in memory. Reusing is safe because following an existing edge does not alter any isEnd flag — "app" stays a valid word.

Step 5 — insert("apple"): branch out 'l','e'
insert "apple"  i=3 'l', i=4 'e'

root
 └─ a
     └─ p
         └─ p [END]        ("app")
             └─ l
                 └─ e [END] ("apple")

At the second p we need child 'l', which is missing, so we create l then e, marking isEnd=true on e. Now two END flags coexist: one mid-path for "app" and one at the leaf for "apple". Branching from an existing node is safe — it extends the tree without disturbing the shorter word.

Step 6 — search("app") → true
walk a → p → p, then check isEnd

root
 └─ a ✓
     └─ p ✓
         └─ p ✓ [END]  <-- isEnd=true ⇒ TRUE

We follow a, p, p — every child exists — and land on the second p. Because its isEnd flag is true, "app" is a stored word and we return true. The flag check is essential: reaching a node only proves the prefix exists, not that the whole string was inserted as a word.

Step 7 — search("ap") → false
walk a → p, then check isEnd

root
 └─ a ✓
     └─ p ✓   <-- first 'p', isEnd=false ⇒ FALSE

We successfully walk a then p, landing on the first p (child of a), so the prefix "ap" exists — but that node's isEnd is false, so "ap" was never inserted as a complete word and we return false. This is exactly why search and startsWith differ: same walk, but search also demands isEnd.

Step 8 — startsWith("app")→true; search("appl")→false; search("banana")→false
startsWith("app"): walk a→p→p
  node reached ⇒ TRUE (ignore isEnd)

search("appl"): walk a→p→p→l
  node reached but isEnd=false ⇒ FALSE

search("banana"): root has no 'b'
  child missing mid-walk ⇒ FALSE

startsWith("app") only needs the path to exist, so reaching the node returns true. search("appl") reaches the real node l but its isEnd is false → false. search("banana") fails immediately when child 'b' is missing under root — bailing on a missing child is safe because no path means no possible match.

🎯 Guided practice

  1. Easy — Implement Trie (Prefix Tree): insert, search, startsWith.

    Step 1 — Node shape. Each TrieNode = an array children[26] (index c - 'a') plus boolean isEnd. The Trie holds a single empty root.

    Step 2 — insert(word). Start node = root. For each char c: i = c - 'a'; if node.children[i] is null, create a new node there; move node = node.children[i]. After the loop, set node.isEnd = true. This carves a path and plants the end-of-word marker.

    Step 3 — search(word). Walk the same way; if any children[i] is null, return false. At the end, return node.isEnd (the path existing isn't enough — it must be a real word).

    Step 4 — startsWith(prefix). Identical walk, but at the end just return true — we only care that the path exists.

    Core pattern learned: all three operations are the same O(L) downward walk; only the final check differs (isEnd vs. nothing). That distinction is the whole trick, and it underlies every problem below.

  2. Medium — Design Add and Search Words Data Structure. Same as Implement Trie, but search may contain ., which matches any single character.

    Step 1 — Reuse insert. addWord is the plain insert from above.

    Step 2 — Recursive search. Write dfs(node, word, idx). If idx == word.length, return node.isEnd. Let c = word[idx]. If c is a literal letter, recurse into the single child node.children[c-'a'] (false if null). If c == '.', loop over all 26 children and return true if any non-null child returns true from dfs(child, word, idx+1).

    Step 3 — Complexity. A literal-only query is O(L). A query with dots can branch: worst case (all dots) is O(Σ^L), but each literal between dots prunes the search to one branch.

    Core pattern learned: the wildcard turns a linear walk into a DFS that fans out into all children at a wildcard — the reusable move for any "match with blanks" string problem.

  3. Medium — Search Suggestions System. Given products and a search word typed one char at a time, after each prefix return up to 3 lexicographically smallest matching products.

    Step 1 — Recognize the pattern. "As the user types" + "matching prefix" = Trie. We want, for every prefix of the search word, the 3 smallest completions.

    Step 2 — Build. Sort products lexicographically, then insert each into a Trie. Sorting first means a DFS that visits children in a..z order reaches words in sorted order, so the first 3 it collects at any node are automatically the 3 smallest.

    Step 3 — Query. Walk the search word character by character. At each character, descend to the corresponding child; from that node run a bounded DFS that stops after 3 completed words, and emit that list. If at any character the child is missing, the path is broken — every remaining prefix yields an empty list.

    Step 4 — Complexity & optimization. Building is O(total chars). A query over a search word of length W does W descents, each followed by a DFS that collects ≤3 words of length ≤L, so roughly O(W·L). The standard speedup: store a precomputed top-3 list at each node during insert, making each query step O(1) lookup. Note that for this specific problem a sort-then-binary-search-the-prefix-range solution is equally idiomatic and often the expected one; the Trie shines when input is truly streaming or shared across many queries.

    Core pattern learned: sort-then-Trie gives ordered suggestions for free, and a bounded DFS from the prefix node is the reusable "collect completions" move that also powers autocomplete and (with the wildcard DFS from the previous problem) partial-match search.

✨ Added by the guide — work these before the full problem set.

Lessons in this topic

🧠 Review & recall

Active recall is what moves a topic into long-term memory. Flip each card before revealing, then test yourself — your results are saved on this device.

Flashcard
What is a Trie (prefix tree) and what is its trigger signal — when should you reach for one?
tap to reveal →
A Trie stores a set of strings as a tree of characters where every path from the root spells a prefix and words sharing a prefix share nodes. Reach for it whenever a problem revolves around prefixes: autocomplete / search suggestions, 'does any stored word start with X', wildcard word matching, or repeatedly querying many words against one shared dictionary.
💡 Trie = retrieval; think 'shared-prefix tree for prefix questions'.
Flashcard
How is a TrieNode structured, and what is the role of the isEnd flag?
tap to reveal →
Each TrieNode holds up to 26 child pointers (children[26], index c-'a' for lowercase a-z) plus a boolean isEnd flag. isEnd marks where a complete word terminates — a node merely existing only proves a prefix exists, not that a whole word was inserted.
💡 26 child slots + 1 'I'm a real word' flag.
Flashcard
What are the time complexities of insert, search, and startsWith in a Trie, and how do search and startsWith differ?
tap to reveal →
All three are an O(L) downward walk where L is the word/prefix length, independent of how many words are stored. They do the identical walk; only the final check differs: search returns node.isEnd (the path must spell a real word), while startsWith just returns true once the path exists.
💡 Same O(L) walk — search demands isEnd, startsWith doesn't.
Flashcard
In 'Design Add and Search Words', how does the '.' wildcard change the search, and what is the resulting complexity?
tap to reveal →
addWord is a plain insert. search becomes a recursive dfs(node, word, idx): a literal letter recurses into one child, but '.' loops over all 26 children and returns true if any branch matches. A literal-only query is O(L); a query with dots can branch, worst case O(Σ^L), though literals between dots prune the search.
💡 Dot = fan out into all 26 children (DFS), letter = follow one.
Flashcard
How does a Trie solve 'Search Suggestions System' and why sort the products first?
tap to reveal →
Sort products lexicographically, then insert each into the Trie. Walk the search word character by character; at each prefix, run a bounded DFS from that node that stops after collecting 3 completed words. Because children are visited in a..z order, a DFS over a pre-sorted Trie reaches words in sorted order, so the first 3 collected are automatically the 3 lexicographically smallest.
💡 Sort-then-Trie = ordered suggestions for free; bounded DFS stops at 3.
Flashcard
How is a Trie used in 'Index Pairs of a String' to find all (including overlapping) word occurrences?
tap to reveal →
Insert all words into the Trie. For each start index i in text, walk a pointer p from the root following text characters; break the inner loop on a missing child. Whenever p.isEnd is true, record [i, currentIndex] as a match. Starting fresh from every index captures overlapping occurrences.
💡 Try every start index; record [i,j] each time isEnd lights up.
Q1. In a Trie, search("ap") after only "apple" was inserted returns false even though the path a→p exists. Why?
Q2. When inserting "apple" into a Trie that already contains "app", what happens to the shared prefix "app"?
Q3. For 'Design Add and Search Words', searching for "......" (six dots) after adding "banana" returns true. What is the search doing at each dot?
Q4. What does sorting the products list before building the Trie buy you in 'Search Suggestions System'?
Q5. In the Trie-based 'Index Pairs' approach on text="programmingisfun" with words=["pro","is","fun","gram"], how are matches like [0,2] for "pro" detected?