Trie Search

This visualization demonstrates how to search for a word in a trie (prefix tree) by following the path of characters from the root down through the tree. At each step, the algorithm looks for the next character among the current node's children, either finding a match and continuing deeper or failing and reporting that the word does not exist. Trie search is the fundamental lookup operation that makes tries practical for applications from autocomplete to spell checking to network routing.

How It Works

1. Start at root: Begin at the root node, which represents the empty string.
2. Follow the character path: For each character in the search word, check if the current node has a child labeled with that character.
   • If yes, move to that child node and advance to the next character.
   • If no, the word is not in the trie -- the search fails immediately. There is no need to examine the rest of the characters.
3. Check end-of-word marker: After successfully following the path for all characters, check whether the current node is marked as the end of a word.
   • If marked, the word exists in the trie -- the search succeeds.
   • If not marked, the search string is a prefix of some longer word in the trie but was never inserted as a complete word itself. For example, if "CARD" is in the trie but "CAR" was never inserted, searching for "CAR" reaches the R node but finds no end-of-word marker.

Consider searching for "CARE" in a trie containing "CAR," "CARD," "CARE," and "CATS." The algorithm starts at the root, follows C to A to R to E, and finds the end-of-word marker at E -- search succeeds. Now consider searching for "COP." The algorithm follows C, then looks for O among C's children. If O is not present (because no word starting with "CO" was inserted), the search fails immediately at the second character.

Complexity

The critical insight is that search time depends only on the length of the search word, not on the number of words stored in the trie. Whether the trie contains 100 words or 1 million words, searching for a 5-character word takes exactly 5 node lookups. This is a significant advantage over balanced BSTs, where string comparison at each node takes O(L) time and there are O(log n) comparisons, giving O(L log n) total time for a search among n strings.

Search vs. Prefix Check

Trie search supports two distinct queries. Exact word search follows the full path and checks the end-of-word marker, as described above. Prefix check follows the path but does not require the end-of-word marker -- it only needs to confirm that the path exists. If the path exists, at least one word in the trie starts with that prefix. This distinction is the foundation of autocomplete: as the user types each character, a prefix check confirms whether any completions exist, and a subtree enumeration collects them.

Failure Modes and Early Termination

Trie search fails fast. If the search word contains a character not present in the trie at the expected position, the algorithm terminates immediately without examining the remaining characters. In practice, this means that searches for words with uncommon prefixes fail in just one or two steps, regardless of the word's total length. This early termination property makes tries efficient for negative lookups (confirming a word is not present), which is particularly valuable in spell checkers where most candidate corrections are not valid words.

Real-World Applications

Autocomplete systems perform prefix checks as the user types, then enumerate all words in the subtree below the prefix node to generate suggestions, often ranking them by frequency or recency. Dictionary lookup in word games (like Scrabble solvers) uses trie search to validate candidate words and prefix checks to prune invalid branches during word generation. Spell checkers combine trie search with edit distance algorithms: for a misspelled word, the checker explores trie paths that differ by one or two characters (insertions, deletions, substitutions) to find valid corrections. Network routers use trie search for longest prefix matching, finding the most specific routing rule that matches an IP address.

When to Use

Use trie search whenever you need fast string lookup with prefix support. It is the natural choice for autocomplete, dictionary validation, prefix-based filtering, and any scenario where lookup time must be independent of the dictionary size. For exact-match-only lookups without prefix requirements, a hash table is simpler and uses less memory.