Word Search in Trie in DSA C++

Mental Model

A trie stores words by sharing common prefixes, making it easy to check if a word exists by following the path of letters.

Analogy: Imagine a tree where each branch is a letter, and walking down branches spells out words. To find a word, you just follow the branches matching each letter.

root
 ↓
 a -> p -> p -> l -> e [end]
      ↓
      e -> null

Each arrow points to the next letter node. The [end] marks a complete word.

Dry Run Walkthrough

Input: Insert words: "apple", "app", then search for "app"

Goal: Check if the word "app" exists in the trie after inserting "apple" and "app"

Step 1: Insert 'apple' letter by letter

root -> a -> p -> p -> l -> e [end]
root is empty initially

Why: We build the path for 'apple' so we can find it later

Step 2: Insert 'app' letter by letter, reusing existing nodes

root -> a -> p -> p [end]
           ↓
           l -> e [end]

Why: We reuse 'a', 'p', 'p' nodes and mark 'p' as end for 'app'

Step 3: Search for 'app' by following nodes

root -> a -> p -> p [end]
search ends at node marked end

Why: Finding 'app' means all letters exist and last node marks word end

Result:

root -> a -> p -> p [end]
           ↓
           l -> e [end]
Search result: true

Annotated Code

DSA C++

#include <iostream>
#include <string>
using namespace std;

class TrieNode {
public:
    TrieNode* children[26];
    bool isEndOfWord;

    TrieNode() {
        for (int i = 0; i < 26; i++) children[i] = nullptr;
        isEndOfWord = false;
    }
};

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

    void insert(const string& word) {
        TrieNode* curr = root;
        for (char c : word) {
            int index = c - 'a';
            if (!curr->children[index])
                curr->children[index] = new TrieNode();
            curr = curr->children[index]; // advance curr to next letter node
        }
        curr->isEndOfWord = true; // mark end of word
    }

    bool search(const string& word) {
        TrieNode* curr = root;
        for (char c : word) {
            int index = c - 'a';
            if (!curr->children[index])
                return false; // letter missing, word not found
            curr = curr->children[index]; // advance curr to next letter node
        }
        return curr->isEndOfWord; // check if last node marks word end
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    cout << boolalpha << trie.search("app") << endl;
    return 0;
}

curr = curr->children[index]; // advance curr to next letter node

advance curr pointer to next letter node to build or traverse path

curr->isEndOfWord = true; // mark end of word

mark current node as end of a valid word

if (!curr->children[index]) return false; // letter missing, word not found

stop search early if next letter node does not exist

return curr->isEndOfWord; // check if last node marks word end

confirm word exists only if last node marks end

Output

true

Complexity Analysis

Time: O(m) because we process each of the m letters in the word once during insert or search

Space: O(m) for insert because we may create up to m new nodes for a new word

vs Alternative: Compared to searching words in a list (O(n*m)), trie search is faster as it depends only on word length, not number of words

Edge Cases

search for a word not inserted

search returns false because path breaks before end

DSA C++

if (!curr->children[index]) return false; // letter missing, word not found

insert empty string

marks root as end of word, allowing empty word search

DSA C++

curr->isEndOfWord = true; // mark end of word

search for prefix that is not a word

returns false because last node is not marked end

DSA C++

return curr->isEndOfWord; // check if last node marks word end

When to Use This Pattern

When you need to quickly check if words or prefixes exist in a large set, use a trie because it shares common prefixes and speeds up search.

Common Mistakes

Mistake: Not marking the end of word node, causing search to fail for words that are prefixes of others
Fix: Always set isEndOfWord = true at the last node of inserted words

Mistake: Returning true if all letters exist without checking isEndOfWord, causing false positives
Fix: Check isEndOfWord to confirm the word ends exactly at that node

Summary

Stores words by shared prefixes to enable fast word search.

Use when you want quick lookup of words or prefixes in a dictionary.

The key is marking nodes that end words to distinguish full words from prefixes.