SEARCH(word): traverse, return node.isEnd at last char
STARTSWITH(prefix): traverse, return true if prefix exists
Section 2 -- The Idea, Step by Step
Start here (middle school). Think about how your phone finishes your typing. You tap c, then a, and it already offers "cat," "car," and "card." It can do that because words that begin the same way are stored along the same path. A trie (say "try," from retrieval) is exactly that: a tree built out of letters, where every shared beginning is written down only once. Walk down the branch c → a → t and you have spelled "cat."
Build it up (high school). Three things describe the job: the length of a word $L$, the size of the alphabet $\Sigma$ (26 for lowercase English), and how many words are stored $n$. The key move is simple -- to insert or find a word you take one step per letter, following or creating the matching child. So the work is just the number of letters: $$T = O(L).$$ Searching "cat" costs 3 steps whether the trie holds 10 words or 100,000. A tiny flag called isEnd on the last node marks "a real word ends here," so the "car" hiding inside "card" isn't mistaken for a stored word.
Go deeper (AP / intro-college). Each node carries up to $\Sigma$ child pointers plus the isEnd flag. Insert, search, and startsWith are all $O(L)$ and -- crucially -- independent of $n$, whereas a binary search over a sorted array of strings costs $O(L\log n)$. The price is memory: worst case $O(\Sigma\, n\, L)$ pointers, which is why real implementations swap the fixed 26-slot array for a hash map holding only the children that actually exist. Prefix search is the whole reason a trie wins -- reach the prefix node in $O(L)$, then gather every word in its subtree, giving autocomplete in $O(L + \text{matches})$.
Try this in the sim above. (1) Press Next one step at a time and watch which pseudocode line lights up -- follow the INSERT loop advancing one character per step. (2) Drag the n slider up and notice the Operations / Comparisons counters climb, yet any single search still only touches $L$ letters, never $n$. (3) Switch the preset between Sorted and Reverse to feed a different set of keys, then press Reset to re-run.
Section 3 -- Complexity Analysis
Symbol
Meaning
n
Input size
T(n)
Time complexity function
h
Height or depth of structure
k
Key or rank parameter
W(n)
Worst-case complexity
A(n)
Average-case complexity
Step 1 -- Structure. A trie (prefix tree) is a tree where each node represents a character, and each path from root to a marked node represents a word. Root represents empty string. Node has up to 26 children (for lowercase English). Space: O(SIGMA * n * L) where SIGMA=alphabet size.
Step 2 -- INSERT O(L). Traverse character by character. Create new node if character not present. Mark last node as end-of-word. L = word length. No comparisons between words needed.
Step 3 -- SEARCH O(L). Traverse character by character. If any character is missing: not found. If all characters found: check isEnd flag. O(L) -- independent of number of words stored.
Step 4 -- STARTSWITH O(L). Same as SEARCH but does not check isEnd at end. Just verifies the prefix path exists. O(L).
Step 5 -- Space O(SIGMA * n * L). Each word of length L can create up to L new nodes, each with SIGMA pointers. For n words, worst case: n*L nodes, each with SIGMA children. Common optimization: use HashMap for children instead of fixed-size array -- O(actual keys) space.
Step 6 -- Applications. Autocomplete: traverse prefix, enumerate all words in subtree. Spell checking. IP routing (binary trie on IP address bits). Pattern matching. Word games (Boggle, Scrabble valid-word check). Longest common prefix of a set of strings.
Section 4 -- FAQ
Why is trie search O(L) and not O(n)? concept+
Trie search does NOT depend on n (number of words stored). It only traverses L characters. This is faster than binary search O(L log n) when comparing strings character by character. The trie trades space for time -- all shared prefixes are stored once.
How does autocomplete use a trie? applied+
Insert all dictionary words. For a prefix query: traverse to the prefix node in O(L). Then DFS/BFS the subtree to collect all words -- O(number of results). Total: O(L + output size). Used in Google Search suggestions, IDE code completion, URL bar.
When to use trie vs hash map for strings? nonobv+
Hash map: O(L) average insert/search (compute hash), O(L*n) space. Trie: O(L) worst-case, shares prefixes, supports prefix queries. Use trie for prefix search, lexicographic ordering, or when many strings share common prefixes. Use hash map for exact-match only and when prefix operations not needed.
What is a compressed trie (radix tree)? complex+
A compressed trie merges nodes that have only one child into a single node storing a string label. Reduces n*L nodes to at most 2n-1 nodes. Patricia trie is a specific compressed binary trie. Used in Linux kernel for routing tables, Go's net/http router.
How does a binary trie work for integers? deep+
Instead of 26 children, each node has 2 children (bit 0 and bit 1). Insert integer bit by bit from MSB to LSB. Supports: XOR maximization (find pair with max XOR), prefix queries on binary representations. Used in competitive programming for XOR problems.
How to delete a word from a trie? concept+
Set isEnd=false at the word's last node. If the node has no children and isEnd=false, it is now useless -- delete it and recurse upward to parent. Continue deleting childless non-end nodes up to root. This cleanup ensures trie doesn't retain unnecessary nodes.
Section 5 -- Common Misconceptions
Conceptual Misconceptions
X Trie search is O(L * n) because it checks all n words.
O Trie search is O(L) independent of n. Traversal follows only one path based on characters -- never backtracks to try other words.
X Trie uses less memory than hash map.
O Trie with fixed SIGMA=26 children: 26 pointers per node. For short, non-overlapping words, hash map may use less memory. Trie saves memory only when many words share long prefixes.
X A trie can only store lowercase English.
O Use different child sizes: 26 for lowercase, 128 for ASCII, 65536 for Unicode. Or use HashMap for sparse alphabets.
Implementation Errors
X Forgetting to mark isEnd=true after insert.
O Without isEnd, SEARCH returns false for words that were inserted. isEnd distinguishes word end from prefix-only nodes.
X Checking children array for null vs checking character existence.
O children[c] is null means character c not present in this position. Must null-check before traversing. Accessing null node causes NullPointerException.
X Using node count to estimate memory -- ignoring pointer overhead.
O Each TrieNode has 26 pointers (8 bytes each on 64-bit = 208 bytes/node) plus isEnd. For n=10^5 length-10 words: potentially 10^6 nodes * 208 bytes = 208 MB. HashMap children reduces this to actual characters used.