Trie Search: Exact Match Queries
What You'll Learn
You'll learn how to implement a search operation that determines whether a complete word exists in your trie by traversing character-by-character along the stored paths.
The Core Idea
Now that you can insert words into a trie, the next natural operation is searching for exact matches. Given a query word, you want to answer: "Does this exact word exist in my trie?"
The search process mirrors insertion, but instead of creating nodes, you follow existing links:
- Start at the root with the first character of your search word
- Follow the path: For each character, check if a child link exists
- If any link is missing, the word doesn't exist — return false immediately
- If you reach the end of the word, check the final node's
isEndOfWordflag
The crucial detail: reaching the final character isn't enough! The node must be marked as a word ending. Otherwise, you might be matching a prefix of a stored word, not the word itself.
Example Walkthrough
Suppose your trie contains "cat" and "catch". Searching for "cat":
- Follow
c→a→t(all links exist) - Check if the
tnode hasisEndOfWord = true - It does! Return true
Searching for "ca":
- Follow
c→a(links exist) - But the
anode hasisEndOfWord = false - Return false (it's only a prefix)
Time and Space
Search runs in O(m) time, where m is the length of the search word — you touch at most one node per character. No extra space is needed beyond a few variables.
Key Takeaway: Trie search verifies exact word existence by following character links and confirming the final node is marked as a word ending, running in time proportional to word length regardless of how many words the trie stores.