Introduction to tries - searching for words

You're in a technical interview at Amazon when the interviewer asks you to implement a search method for a Trie. "We've already built the insert method," they say. "Now make the search work." This problem, also known as "Implement Trie (Prefix Tree) Search" on other platforms, tests whether you understand how prefix trees store and retrieve words. It's a foundational data structures question that companies like Amazon love because it reveals how well you grasp hierarchical string storage.

TL;DR

To search for a word in a Trie, start at the root and traverse one node per character using the children HashMap. If any character is missing from the current node's children, return false immediately. After processing all characters, return the isWordBoundary flag on the final node. This distinguishes complete words from prefixes that happen to exist in the tree. The search runs in O(k) time where k is the word length, independent of how many words the Trie contains.

Why This Problem Matters

Tries are one of those data structures that seem niche until you realize they're everywhere. Every time you type in a search bar and see autocomplete suggestions, there's likely a Trie (or a variant) working behind the scenes. Understanding how to search a Trie builds the foundation for more complex operations like prefix matching, wildcard search, and even building things like spell checkers. If you can nail the search method, you already understand the traversal pattern that applies to nearly every Trie operation.

What Is a Trie?

A Trie (pronounced "try," derived from "retrieval") is a tree-shaped data structure designed for efficient string lookups. Unlike a binary tree where each node has at most two children, a Trie node can have up to 26 children (for uppercase English letters), one for each possible next character.

The real power of a Trie comes from shared prefixes. Words that start the same way share the same path from the root. Let's look at a Trie containing the words FIRE, FIRECODE, and FIRESIDE:

Notice how all three words share the path F-I-R-E from the root. The asterisk (*) on certain nodes marks a word boundary, meaning a complete word ends at that node. This is the critical detail that makes search work correctly.

Without word boundaries, you couldn't distinguish between a word that was actually inserted and a prefix that just happens to exist as part of a longer word. The node for E after F-I-R is marked as a word boundary because FIRE was inserted, but the node for S after F-I-R-E is not, because FIRES was never inserted.

Understanding the Problem

Given a partially implemented Trie class with a working insert method, we need to implement search, which takes a word and returns true if the complete word was previously inserted, false otherwise.

Here's how the TrieNode class looks:

class TrieNode {
  Character c;                              // The character at this node
  Boolean isWordBoundary = false;           // True if a word ends here
  Map<Character, TrieNode> children = new HashMap<>();  // Child nodes
}

And the test cases that define the expected behavior:

The distinction between the last three cases is important. "FIRES" fails not because the characters don't exist in the Trie (they do, as part of "FIRESIDE"), but because the node for S was never marked as a word boundary. "CODE" fails for a different reason: the root has no child node for the character C at all.

Solution Approach

The search algorithm mirrors the insert algorithm closely. If you study the provided insert method, you'll notice it traverses the Trie character by character, creating nodes as needed. Search does the same traversal but instead of creating missing nodes, it returns false when a node is missing.

Here's the thought process:

1. Start at the root node
2. For each character in the search word, check if the current node has a child for that character
3. If the child exists, move to it. If not, the word can't be in the Trie, so return false
4. After processing all characters, check the isWordBoundary flag. This is the step that separates "word search" from "prefix search"

Let's trace through searching for "FIRE":

Each step advances the node pointer to the child matching the current character. After all four characters are processed, we check isWordBoundary on the final node. Since FIRE was inserted as a complete word, that flag is true.

Now let's visualize the successful search path on the Trie itself:

The green path shows the traversal from root through F, I, R, to E. The E node is marked with an asterisk because it's a word boundary. The search returns true.

What about searching for "FIRES"?

The red path traces through F, I, R, E, and reaches S. All characters were found, but S is NOT a word boundary (no asterisk). The search returns false. This is the subtlety that trips up many candidates: successfully traversing all characters is necessary but not sufficient.

And searching for "CODE"? The root node only has F as a child. There's no C, so we return false on the very first character.

Implementation

Prefer a different language? Jump to solutions in other languages.

public Boolean search(String word) {
    // Start at the root of the Trie
    TrieNode node = root;

    // Traverse the Trie character by character
    for (int i = 0; i < word.length(); i++) {
        char c = word.charAt(i);
        // If no child exists for this character, the word isn't in the Trie
        if (!node.children.containsKey(c)) return false;
        // Move to the child node
        node = node.children.get(c);
    }

    // All characters matched - but is this a complete word or just a prefix?
    return node.isWordBoundary;
}

The entire method is just a loop with a HashMap lookup at each step and a final boolean check. There's a satisfying symmetry with insert: where insert creates missing children and marks the last node as a word boundary, search checks for missing children and reads the word boundary flag.

Why Return isWordBoundary Instead of true?

This is the most common mistake I see candidates make. After successfully traversing all characters, it's tempting to simply return true. But consider searching for "FIRECO" in our Trie. The path F-I-R-E-C-O exists (it's part of FIRECODE), and every character check succeeds. Returning true at this point would be wrong because "FIRECO" was never inserted as a word. The isWordBoundary flag is the only thing that distinguishes a complete word from a prefix of a longer word.

Complexity Analysis

Time Complexity: O(k)

Where k is the length of the search word. We perform exactly k iterations, each involving a HashMap lookup that runs in O(1) average time. This is what makes Tries compelling: the search time depends only on the word length, not on how many words are stored. Whether your Trie holds 10 words or 10 million, searching for "FIRE" always takes 4 steps.

Compare this to scanning a list of n words, which would take O(n * k) in the worst case, checking each word character by character.

Space Complexity: O(n * k)

The Trie itself consumes O(n * k) space where n is the number of stored words and k is the average word length. Each unique character along each unique path requires its own TrieNode with a HashMap. The search method itself uses O(1) extra space since it only maintains a single node pointer.

In practice, shared prefixes reduce the actual memory footprint significantly. Our three words (FIRE, FIRECODE, FIRESIDE) share the prefix F-I-R-E, saving 4 nodes compared to storing them independently.

Common Pitfalls

1. Returning true instead of isWordBoundary: The single most common mistake. Always check the word boundary flag after traversal. Without it, prefixes of longer words would incorrectly return true.

2. Confusing the search and prefix-search methods: A Trie typically supports both search(word) (exact word match) and startsWith(prefix) (prefix existence). The only difference is the return statement: search returns node.isWordBoundary, while startsWith returns true after successful traversal.

3. Forgetting to handle the empty string: If someone calls search(""), the loop never executes, and we return root.isWordBoundary. Since the root is never marked as a word boundary (unless you explicitly insert an empty string), this correctly returns false.

4. Modifying the root reference: Use a separate iterator variable (node) to traverse. Accidentally reassigning root would corrupt the entire Trie for future operations.

Interview Tips

When this problem comes up in an interview:

1. Start by studying the provided code. The insert method and TrieNode class are given. Understanding how insert works makes search almost trivial to derive.

2. Ask about character constraints. In this problem, all characters are uppercase. This matters for real implementations where you might need to handle mixed case, digits, or Unicode.

3. Explain the word boundary concept clearly. Interviewers are specifically testing whether you understand why returning true after traversal is wrong. Articulate the difference between "this path exists" and "this path represents a complete word."

4. Mention the prefix-search variant. After implementing search, it's worth noting that a one-line change (return true instead of node.isWordBoundary) gives you prefix matching. This shows breadth of understanding.

5. If asked about follow-ups, common ones include: implementing delete, supporting wildcards (. matching any character), or finding all words with a given prefix (autocomplete). Each builds on the same traversal pattern.

Key Takeaways

• Trie search runs in O(k) time where k is the word length, making lookups independent of how many words are stored. This is the core advantage over list-based or HashSet-based approaches when prefix operations are needed.
• The isWordBoundary flag is what distinguishes a complete word from a prefix. Returning true after successful character traversal is the most common bug in Trie implementations.
• Search mirrors insert: where insert creates missing nodes and marks boundaries, search checks for missing nodes and reads boundaries. Study the insert code and the search implementation follows naturally.
• Tries trade space for speed. The O(n * k) memory cost is justified when you need fast prefix queries, autocomplete, or pattern matching that a HashMap alone cannot provide.
• Every Trie operation (search, insert, delete, prefix check) follows the same character-by-character traversal from root to target. Once you understand this traversal, the other operations are straightforward variations.

Practice and Related Problems

Once you're comfortable with Trie search, extend your understanding with these related challenges:

• Implement the startsWith prefix method (one-line change from search)
• Add a delete method that removes words without breaking shared prefixes
• Build autocomplete that returns all words matching a prefix
• Implement wildcard search where . matches any single character

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have sharpened their skills for technical interviews at top companies. If you're preparing for your next interview, consistent practice with data structure problems like this one will make the difference.

Solutions in Other Languages

Python

def search(self, word: str) -> bool:
    node = self.root

    for c in word:
        if c not in node.children:
            return False
        node = node.children[c]

    return node.is_word_boundary

JavaScript

search(word) {
    let node = this.root;

    for (let i = 0; i < word.length; i++) {
        const c = word[i];
        if (!node.children.has(c)) return false;
        node = node.children.get(c);
    }

    return node.isWordBoundary;
}

TypeScript

search(word: string): boolean {
    let node: TrieNode = this.trie.root;

    for (let i = 0; i < word.length; i++) {
        const c = word[i];
        if (!node.children.has(c)) return false;
        node = node.children.get(c)!;
    }

    return node.isWord;
}

C++

bool search(string word) {
    TrieNode* node = root;

    for (int i = 0; i < word.length(); i++) {
        char c = word[i];
        if (node->children.find(c) == node->children.end()) return false;
        node = node->children[c];
    }

    return node->isWordBoundary;
}

Go

func (t *Trie) search(word string) bool {
    node := t.root

    for _, c := range word {
        if _, exists := node.children[c]; !exists {
            return false
        }
        node = node.children[c]
    }

    return node.isWordBoundary
}

Scala

def search(word: String): Boolean = {
    var node = root

    for (i <- 0 until word.length) {
        val c = word.charAt(i)
        if (!node.children.contains(c)) return false
        node = node.children(c)
    }

    node.isWordBoundary
}

Kotlin

fun search(word: String): Boolean {
    var node = root

    for (i in 0 until word.length) {
        val c = word[i]
        if (c !in node.children) return false
        node = node.children[c]!!
    }

    return node.isWordBoundary
}

Swift

func search(_ word: String) -> Bool {
    var node = root

    for c in word {
        guard let child = node.children[c] else { return false }
        node = child
    }

    return node.isWordBoundary
}

Ruby

def search(word)
    node = @root

    word.each_char do |c|
        return false unless node.children.key?(c)
        node = node.children[c]
    end

    node.is_word_boundary
end

Rust

fn search(&self, word: &str) -> bool {
    let mut node = &self.root;

    for c in word.chars() {
        match node.children.get(&c) {
            Some(child) => node = child,
            None => return false,
        }
    }

    node.is_word_boundary
}

C#

public bool search(string word) {
    var node = trie.root;

    foreach (char c in word) {
        if (!node.children.ContainsKey(c)) return false;
        node = node.children[c];
    }

    return node.isWord;
}

Dart

bool search(String word) {
    TrieNode node = root;

    for (int i = 0; i < word.length; i++) {
        String c = word[i];
        if (!node.children.containsKey(c)) return false;
        node = node.children[c]!;
    }

    return node.isWordBoundary;
}

PHP

public function search(string $word): bool {
    $node = $this->root;

    foreach (str_split($word) as $char) {
        if (!isset($node->children[$char])) return false;
        $node = $node->children[$char];
    }

    return $node->isWordBoundary;
}