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.

Practice

1. What does the search operation in a Trie data structure do?

easy

A. Checks if a given word exists in the Trie

B. Deletes a word from the Trie

C. Inserts a new word into the Trie

D. Counts the total words stored in the Trie

Solution

1. Step 1: Understand the purpose of search in Trie

   The search operation is designed to check if a specific word is present in the Trie structure.

2. Step 2: Differentiate from other operations

   Insertion adds words, deletion removes words, and counting totals words. Search only checks existence.

3. Final Answer:

   Checks if a given word exists in the Trie -> Option A

4. Quick Check:

   Trie search = check word presence [OK]

Hint: Search checks presence of word, not insertion or deletion [OK]

Common Mistakes:

• Confusing search with insert operation
• Thinking search deletes words
• Assuming search counts words

2. Which of the following is the correct way to check if a character node exists in a Trie during search in C++?

easy

A. if (node->children[ch])

B. if (node->children[ch] == nullptr)

C. if (node->children[ch] != nullptr)

D. if (node->children.find(ch) != node->children.end())

Solution

1. Step 1: Understand Trie children representation

   Trie children are usually stored in a map or unordered_map. To check existence, use find() method.

2. Step 2: Identify correct syntax for existence check

   Using find(ch) != end() confirms if character node exists without creating new nodes.

3. Final Answer:

   if (node->children.find(ch) != node->children.end()) -> Option D

4. Quick Check:

   Use find() to check key existence in map [OK]

Hint: Use find() != end() to check map key existence safely [OK]

Common Mistakes:

• Using node->children[ch] != nullptr causes insertion
• Accessing children[ch] directly creates new node
• Checking children[ch] == nullptr can cause insertion

3. Consider the following C++ Trie search code snippet:

bool search(TrieNode* root, const string& word) {
    TrieNode* node = root;
    for (char ch : word) {
        if (node->children.find(ch) == node->children.end())
            return false;
        node = node->children[ch];
    }
    return node->isEndOfWord;
}

What will be the output of search(root, "cat") if the Trie contains words: "car", "cat", "cap"?

medium

A. true

B. false

C. Compilation error

D. Runtime error

Solution

1. Step 1: Trace search for "cat" in Trie

   Each character 'c', 'a', 't' is found in children nodes. The loop completes without returning false.

2. Step 2: Check isEndOfWord flag at last node

   Since "cat" is inserted, the last node's isEndOfWord is true, so function returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Word "cat" exists in Trie = true [OK]

Hint: If all chars found and isEndOfWord true, search returns true [OK]

Common Mistakes:

• Ignoring isEndOfWord flag and returning true prematurely
• Assuming partial match means word exists
• Confusing false return with missing character

4. Identify the bug in the following Trie search function:

bool search(TrieNode* root, const string& word) {
    TrieNode* node = root;
    for (char ch : word) {
        if (node->children[ch] == nullptr)
            return false;
        node = node->children[ch];
    }
    return node->isEndOfWord;
}

medium

A. Missing check for empty word input

B. Using node->children[ch] in if condition inserts new nodes unintentionally

C. Incorrect return type for search function

D. Loop variable should be int, not char

Solution

1. Step 1: Analyze children access in if condition

   Accessing node->children[ch] creates a new node if it doesn't exist, which is wrong during search.

2. Step 2: Correct way to check existence

   Use find() method to check if child exists without creating new nodes.

3. Final Answer:

   Using node->children[ch] in if condition inserts new nodes unintentionally -> Option B

4. Quick Check:

   Accessing map key directly creates nodes [OK]

Hint: Use find() to check existence, not direct map access [OK]

Common Mistakes:

• Using direct map access in condition causing side effects
• Ignoring empty string edge case
• Wrong loop variable type

5. You have a Trie storing the words: "apple", "app", "application", "bat", "batch". Which of the following search queries will return false?

hard

A. "batch"

B. "app"

C. "appl"

D. "bat"

Solution

1. Step 1: Check if "appl" is a complete word in Trie

   "appl" is a prefix of "apple" and "application" but not a complete word, so isEndOfWord is false.

2. Step 2: Verify other words

   "app", "batch", and "bat" are all complete words stored in the Trie, so search returns true for them.

3. Final Answer:

   "appl" -> Option C

4. Quick Check:

   Prefix only, not full word = false [OK]

Hint: Search returns false for prefixes not marked as words [OK]

Common Mistakes:

• Assuming prefix is always found as word
• Ignoring isEndOfWord flag
• Confusing similar words with exact matches