Trie Search Operation in DSA C++

Mental Model

A trie stores words by linking letters in a tree. Searching means following letters step-by-step to see if the word exists.

Analogy: Imagine a phone book where each letter leads you to the next set of names starting with that letter, like walking down branches of a tree to find a name.

root
 ↓
 t -> r -> e -> e -> [end]
  ↓
  a -> p -> [end]

Dry Run Walkthrough

Input: Trie contains words: "tree", "trap"; search for "trap"

Goal: Check if the word "trap" exists in the trie

Step 1: Start at root, check for 't'

root -> [t] -> r -> e -> e -> [end]
           ↓
           a -> p -> [end]

Why: We must find the first letter to continue searching

Step 2: Move to node 'r', check for 'r'

root -> t -> [r] -> e -> e -> [end]
              ↓
              a -> p -> [end]

Why: Next letter must match to continue down the path

Step 3: Move to node 'a', check for 'a'

root -> t -> r -> [a] -> p -> [end]
                 ↓
                 null

Why: Continue matching letters in the word

Step 4: Move to node 'p', check for 'p'

root -> t -> r -> a -> [p] -> [end]

Why: Last letter matched, check if this node marks end of word

Step 5: Check end of word marker at 'p'

root -> t -> r -> a -> p -> [end]

Why: Confirm word exists only if end marker is true

Result:

root -> t -> r -> a -> p -> [end] (word found: true)

Annotated Code

DSA C++

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;

    TrieNode() : isEndOfWord(false) {}
};

class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(const string& word) {
        TrieNode* curr = root;
        for (char c : word) {
            if (curr->children.find(c) == curr->children.end()) {
                curr->children[c] = new TrieNode();
            }
            curr = curr->children[c];
        }
        curr->isEndOfWord = true;
    }

    bool search(const string& word) {
        TrieNode* curr = root;
        for (char c : word) {
            if (curr->children.find(c) == curr->children.end()) {
                return false; // letter not found
            }
            curr = curr->children[c]; // move to next node
        }
        return curr->isEndOfWord; // check if word ends here
    }
};

int main() {
    Trie trie;
    trie.insert("tree");
    trie.insert("trap");

    cout << boolalpha << trie.search("trap") << endl;
    cout << boolalpha << trie.search("tree") << endl;
    cout << boolalpha << trie.search("trie") << endl;
    cout << boolalpha << trie.search("tra") << endl;

    return 0;
}

if (curr->children.find(c) == curr->children.end()) {

check if current letter node exists to continue search

curr = curr->children[c]; // move to next node

advance pointer to next letter node in trie

return curr->isEndOfWord; // check if word ends here

confirm full word match by checking end marker

Output

true

true

false

false

Complexity Analysis

Time: O(m) because we check each of the m letters in the search word once

Space: O(1) for search as no extra space is used besides pointers

vs Alternative: Compared to searching in a list of words (O(n*m)), trie search is faster because it uses letter-by-letter branching

Edge Cases

search for empty string

returns false because no letters to follow

DSA C++

return curr->isEndOfWord; // check if word ends here

search for word not in trie

returns false immediately when letter missing

DSA C++

if (curr->children.find(c) == curr->children.end()) { return false; }

search for prefix that is not a full word

returns false because end marker is false

DSA C++

return curr->isEndOfWord; // check if word ends here

When to Use This Pattern

When you need to quickly check if a word or prefix exists in a large set of strings, use trie search because it checks letter by letter efficiently.

Common Mistakes

Mistake: Not checking if the current node marks the end of a word after traversing all letters
Fix: Always check the isEndOfWord flag after the loop to confirm full word match

Summary

It checks if a word exists in a trie by following nodes for each letter.

Use it when you want fast word lookups in a dictionary of many words.

The key is to move letter by letter and confirm the word ends exactly at the last letter node.