Word Search in Trie 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 root to leaves represent words.

beginner

How does a Trie help in word search?

A Trie allows fast prefix-based search by traversing nodes corresponding to characters of the word. It can quickly check if a word or prefix exists by following the path in the Trie.

intermediate

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

The time complexity is O(m), where m is the length of the word being searched, because we check one character at each level of the Trie.

beginner

Explain how to insert a word into a Trie.

Start from the root node. For each character in the word, check if a child node exists. If not, create a new node. Move to the child node and continue. Mark the last node as the end of a word.

beginner

What does it mean if a node in a Trie is marked as 'end of word'?

It means that the path from the root to this node forms a complete valid word stored in the Trie.

What does each node in a Trie represent?

A A character of a word

B A whole word

C An integer value

D A number of words

Each node in a Trie represents a single character of a word.

What is the main advantage of using a Trie for word search?

A Uses less memory than arrays

B Fast prefix search

C Stores numbers efficiently

D Sorts words automatically

Trie allows fast prefix-based search by traversing nodes corresponding to characters.

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

A O(m)

B O(1)

C O(log m)

D O(m^2)

Searching a word in a Trie takes O(m) time, where m is the word length.

When inserting a word into a Trie, what do you do if a character node does not exist?

A Skip the character

B Delete the Trie

C Replace the root node

D Create a new node for that character

If a character node does not exist, create a new node for it.

What does marking a node as 'end of word' signify in a Trie?

A The node is empty

B The node is the root

C The path to this node forms a complete word

D The node has no children

Marking a node as 'end of word' means the path from root to this node forms a valid word.

Describe how to search for a word in a Trie step-by-step.

Think about following the path of characters from root to leaf.

Explain why Tries are efficient for prefix-based word searches.

Consider how words with same start share parts of the Trie.