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

Prefix Search and StartsWith Operations

Checking if any word in the trie starts with a given prefix by traversing partial paths.

Prefix Search and StartsWith Operations

What you'll learn: How to check whether any stored word begins with a given prefix by partially traversing a trie.


The Core Idea

Once you've inserted words into a trie, you can efficiently answer "Does any word I've stored start with these letters?" without checking every full word. Instead, you walk down the trie following the prefix letters. If you can successfully traverse all the prefix characters without hitting a dead-end, at least one word starts with that prefix.

Think of it like this: if you're looking up names in a phone book and want to find anyone whose name starts with "Mar," you only need to flip to the M section, then Ma, then Mar — you don't need to read complete names. If that section exists, you've found matches.


How It Works

To implement startsWith(prefix):

  1. Start at the root of your trie
  2. For each character in the prefix:
    • Check if a child node exists for that character
    • If not, return false (no word starts with this prefix)
    • If yes, move to that child node
  3. If you successfully traverse all characters, return true

Notice the difference from exact search: you don't check for an "end of word" marker. You only care whether the path exists, not whether it marks a complete word.


Example

If your trie contains ["apple", "app", "application"]:

  • startsWith("app") → true (all three words match)
  • startsWith("appl") → true (two words match)
  • startsWith("orange") → false (no matching path)

Key Takeaway: Prefix search traverses only as deep as the prefix length, returning true if the path exists—regardless of whether it marks a complete word—making autocomplete and search suggestions extremely efficient.