Word Search in Trie in DSA C++ - Execution Trace

Concept Flow - Word Search in Trie

Start at root node

↓

For each character in word

↓

Check if character exists in current node's children

↓

Move to child node

↓

Repeat for next character

↓

After last character

↓

Check if current node marks end of word

↓

Word FOUND

Start from root, check each character in the word by moving through child nodes. If all characters match and last node marks word end, word is found.

Execution Sample

DSA C++

bool searchWord(TrieNode* root, string word) {
  TrieNode* current = root;
  for (char c : word) {
    if (!current->children[c - 'a']) return false;
    current = current->children[c - 'a'];
  }
  return current->isEndOfWord;
}

This code checks if a word exists in the trie by traversing nodes for each character.

Execution Table

Step	Operation	Current Character	Node Exists?	Move Pointer	Visual State
1	Start at root	-	N/A	current = root	root
2	Check 'c'	'c'	Yes	current = node for 'c'	root -> c
3	Check 'a'	'a'	Yes	current = node for 'a'	root -> c -> a
4	Check 't'	't'	Yes	current = node for 't'	root -> c -> a -> t
5	End of word check	-	N/A	Check isEndOfWord at 't'	root -> c -> a -> t (isEndOfWord = true)
6	Result	-	N/A	Return true	Word found
7	Start at root	-	N/A	current = root	root
8	Check 'd'	'd'	Yes	current = node for 'd'	root -> d
9	Check 'o'	'o'	No	Return false	root -> d (no 'o' child)
10	Result	-	N/A	Return false	Word not found

💡 Traversal stops when a character node is missing or after checking last character's end marker.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 8	After Step 9
current	root	node 'c'	node 'a'	node 't'	node 't'	node 'd'	node 'd'
current->isEndOfWord	false	false	false	true	true	false	false

Key Moments - 3 Insights

Why do we return false immediately when a character node does not exist?

Because if the trie does not have a child node for the current character (see Step 9 in execution_table), the word cannot be formed, so we stop searching.

Why do we check isEndOfWord after the last character?

Because the path may exist but might not represent a complete word. Only if isEndOfWord is true (Step 5) do we confirm the word exists.

What happens if the word is empty?

The search starts and ends at root. Since no characters are checked, the result depends on whether root marks end of a word, usually false.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current node after Step 3 when searching 'cat'?

A Node for 'c'

B Node for 'a'

C Node for 't'

D Root node

💡 Hint

Check the 'Move Pointer' and 'Visual State' columns at Step 3 in execution_table.

At which step does the search for 'dog' fail due to missing node?

A Step 9

B Step 8

C Step 7

D Step 10

💡 Hint

Look for 'Node Exists?' column showing 'No' in execution_table.

If the last node's isEndOfWord was false for 'cat', what would be the search result?

A Word found

B Partial match found

C Word not found

D Error in trie

💡 Hint

Refer to Step 5 and Step 6 in execution_table about isEndOfWord check.

Concept Snapshot

Word Search in Trie:
- Start at root node
- For each character, move to child node if exists
- If any character missing, word not found
- After last char, check isEndOfWord flag
- Return true if flag set, else false

Full Transcript

This visual execution shows how to search a word in a trie. We start at the root node and check each character of the word one by one. If the current character exists as a child node, we move the pointer to that node. If not, we stop and return false because the word cannot be formed. After checking all characters, we verify if the last node marks the end of a word. If yes, the word is found; otherwise, it is not. The execution table traces searching 'cat' successfully and 'dog' failing at the second character. Variable tracker shows how the current pointer moves through nodes. Key moments clarify why missing nodes cause immediate failure and why the end-of-word flag matters. The quiz tests understanding of pointer movement, failure step, and end-of-word significance.

Practice

1. What is the main purpose of using a Trie data structure in word search problems?

easy

A. To store words in a linked list

B. To sort words alphabetically

C. To efficiently store and search words by their prefixes

D. To perform arithmetic operations on words

Solution

1. Step 1: Understand Trie structure

   A Trie stores characters of words in a tree where each node represents a character, allowing prefix sharing.

2. Step 2: Identify Trie use in word search

   Because words share prefixes, Trie allows fast prefix-based search, making word search efficient.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option C

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is best for prefix-based word search [OK]

Common Mistakes:

• Confusing Trie with sorting structures
• Thinking Trie stores words linearly
• Assuming Trie is for arithmetic

2. Which of the following is the correct way to declare a Trie node class in C++ for word search?

easy

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

B. class TrieNode { int data; TrieNode* next; };

C. struct TrieNode { vector<int> children; bool end; };

D. class TrieNode { char letter; TrieNode* left; TrieNode* right; };

Solution

1. Step 1: Check Trie node structure for word search

   Trie nodes typically have an array of pointers for 26 letters and a boolean to mark word end.

2. Step 2: Match with options

   class TrieNode { public: TrieNode* children[26]; bool isEndOfWord; }; matches this structure exactly with children array and isEndOfWord flag.

3. Final Answer:

   class TrieNode { public: TrieNode* children[26]; bool isEndOfWord; }; -> Option A

4. Quick Check:

   Trie node = children array + end flag [OK]

Hint: Trie nodes have 26 children pointers and end flag [OK]

Common Mistakes:

• Using linked list pointers instead of array
• Using vector<int> instead of pointers
• Confusing binary tree node with Trie node

3. What will be the output of the following C++ code snippet that inserts words into a Trie and searches for "cat"?

class TrieNode {
public:
    TrieNode* children[26] = {nullptr};
    bool isEndOfWord = false;
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (!node->children[index])
                node->children[index] = new TrieNode();
            node = node->children[index];
        }
        node->isEndOfWord = true;
    }
    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (!node->children[index])
                return false;
            node = node->children[index];
        }
        return node->isEndOfWord;
    }
};

int main() {
    Trie trie;
    trie.insert("cat");
    trie.insert("car");
    trie.insert("dog");
    cout << (trie.search("cat") ? "Found" : "Not Found") << endl;
    return 0;
}

medium

A. Runtime Error

B. Found

C. Compilation Error

D. Not Found

Solution

1. Step 1: Insert words "cat", "car", "dog" into Trie

   Each word is inserted character by character, creating nodes and marking end of word for last character.

2. Step 2: Search for "cat" in Trie

   Traversal finds nodes for 'c', 'a', 't' and confirms isEndOfWord is true, so returns true.

3. Final Answer:

   Found -> Option B

4. Quick Check:

   Inserted word found = Found [OK]

Hint: Search returns true if end flag is set after traversal [OK]

Common Mistakes:

• Not marking isEndOfWord true on insert
• Returning true without checking end flag
• Off-by-one errors in indexing

4. Identify the bug in the following Trie search function and select the correct fix:

bool search(string word) {
    TrieNode* node = root;
    for (char c : word) {
        int index = c - 'a';
        if (node->children[index])
            return false;
        node = node->children[index];
    }
    return node->isEndOfWord;
}

medium

A. Add a check for null root pointer before loop

B. Remove the return statement inside the loop

C. Change 'node = node->children[index];' to 'node = node->children[index + 1];'

D. Change 'if (node->children[index])' to 'if (!node->children[index])'

Solution

1. Step 1: Analyze the if condition inside loop

   The condition 'if (node->children[index]) return false;' wrongly returns false if child exists, which is opposite logic.

2. Step 2: Correct the condition to check if child does NOT exist

   It should be 'if (!node->children[index]) return false;' to return false when path breaks.

3. Final Answer:

   Change 'if (node->children[index])' to 'if (!node->children[index])' -> Option D

4. Quick Check:

   Check for missing child = return false [OK]

Hint: Return false if child node is missing, not if present [OK]

Common Mistakes:

• Returning false when child exists
• Ignoring null pointer checks
• Incorrect index calculation

5. Given a list of words: ["apple", "app", "application", "bat", "bath", "batman"], how can a Trie be used to efficiently find all words starting with the prefix "app"? Choose the best approach.

hard

A. Insert all words into Trie, then traverse nodes for 'a'->'p'->'p' and collect all descendant words

B. Sort the list and perform binary search for prefix "app"

C. Use a hash map to store all words and check prefix by substring

D. Store words in a linked list and scan each word for prefix match

Solution

1. Step 1: Insert all words into Trie

   Each word is inserted character by character, building a prefix tree.

2. Step 2: Traverse Trie nodes for prefix "app"

   Follow nodes for 'a', 'p', 'p' to reach prefix node, then collect all words below it.

3. Step 3: Collect descendant words

   Perform DFS or BFS from prefix node to gather all words starting with "app" efficiently.

4. Final Answer:

   Insert all words into Trie, then traverse nodes for 'a'->'p'->'p' and collect all descendant words -> Option A

5. Quick Check:

   Trie prefix traversal + collect descendants = Insert all words into Trie, then traverse nodes for 'a'->'p'->'p' and collect all descendant words [OK]

Hint: Traverse prefix nodes then gather descendants in Trie [OK]

Common Mistakes:

• Using sorting instead of Trie for prefix search
• Checking prefix by substring on all words
• Scanning linked list inefficiently