Prefix Search Using Trie in DSA Typescript - 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 nodes represent prefixes or words.

beginner

How does a Trie help in prefix search?

A Trie allows quick prefix search by following the path of characters from the root node. If the prefix exists, all words starting with that prefix are found by traversing the subtree from that node.

intermediate

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

The time complexity is O(m), where m is the length of the prefix. This is because we only traverse nodes corresponding to the prefix characters.

beginner

In a Trie node, what does a boolean flag 'isEndOfWord' represent?

It indicates whether the path from the root to this node forms a complete word stored in the Trie.

intermediate

Why is Trie more efficient than a list for prefix search?

Trie avoids checking every word by branching on characters. It directly follows the prefix path, reducing search time from O(n*m) in a list (n words, m prefix length) to O(m) in a Trie.

What does each node in a Trie typically represent?

A A single character

B A whole word

C A number

D A sentence

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

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

A Sorts words automatically

B Faster prefix lookup by character traversal

C Stores numbers efficiently

D Uses less memory than arrays

Trie allows fast prefix search by following nodes for each character in the prefix.

If a prefix does not exist in a Trie, what happens during search?

A Returns the root node

B Returns all words

C Throws an error

D Search ends early with no matches

If the prefix path is missing, the search stops early indicating no words with that prefix.

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

A End of a valid word

B Start of a word

C Node has children

D Node is root

It marks that the path to this node forms a complete stored word.

What is the time complexity to insert a word of length m into a Trie?

A O(n)

B O(1)

C O(m)

D O(m*n)

Insertion requires traversing or creating nodes for each character, so O(m).

Explain how prefix search works using a Trie data structure.

Think about following the path of characters from root to find prefix matches.

Describe the structure of a Trie node and its role in prefix search.

Focus on what each node holds and how it connects to others.