Knowledge Guide
Home › DSA

Trie

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

0 / 10 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