Course contentsShow
← Computer Science
Lesson 622 of 2,87215. Tries and Specialized TreesFree lesson

Trie Search: Exact Match Queries

Implementing search to determine if a complete word exists in the trie by following character links.

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:

  1. Start at the root with the first character of your search word
  2. Follow the path: For each character, check if a child link exists
  3. If any link is missing, the word doesn't exist — return false immediately
  4. If you reach the end of the word, check the final node's isEndOfWord flag

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 t node has isEndOfWord = true
  • It does! Return true

Searching for "ca":

  • Follow c → a (links exist)
  • But the a node has isEndOfWord = 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.