Trie Search Operation in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie data structure?

A Trie is a tree-like data structure used to store a dynamic set of strings where keys are usually strings. Each node represents a character, and paths from the root to leaves represent words.

beginner

What does the search operation in a Trie do?

The search operation checks if a given word exists in the Trie by following nodes corresponding to each character of the word. If all characters are found and the last node marks the end of a word, the search returns true.

beginner

In Trie search, what happens if a character node is missing during traversal?

If a character node is missing while traversing the Trie for a word, it means the word does not exist in the Trie, so the search returns false immediately.

intermediate

Why does Trie search have a time complexity of O(m), where m is the length of the word?

Because the search operation checks each character of the word once by moving down the Trie nodes, the time depends only on the word length, not the number of words stored.

beginner

What is the role of the 'isEndOfWord' flag in Trie nodes during search?

The 'isEndOfWord' flag indicates if the current node marks the end of a valid word. During search, even if all characters match, the word is considered found only if this flag is true at the last character node.

What does the Trie search operation return if a character node is missing?

A True

B Returns null

C It continues searching

D False

If a character node is missing during traversal, the word does not exist in the Trie, so search returns false.

What does the 'isEndOfWord' flag signify in a Trie node?

A Start of a word

B Middle of a word

C End of a valid word

D Node is empty

The 'isEndOfWord' flag marks that the node represents the end of a valid word stored in the Trie.

What is the time complexity of searching a word of length m in a Trie?

A O(1)

B O(m)

C O(n)

D O(m*n)

Trie search time depends on the length of the word m, so it is O(m).

If a Trie contains the words 'cat' and 'car', what will searching for 'ca' return?

A False

B Depends on implementation

C True

D Error

Even though 'ca' is a prefix, it is not a complete word in the Trie unless 'isEndOfWord' is true at 'a' node, so search returns false.

During Trie search, what is the first step for each character in the word?

A Check if the character node exists among children

B Add the character node

C Delete the character node

D Mark the node as end of word

For each character, search checks if the corresponding child node exists to continue traversal.

Explain how the search operation works in a Trie data structure.

Think about following the path of characters and checking the end marker.

Why is Trie search efficient compared to searching in a list of words?

Consider how Trie organizes words by common prefixes.