Prefix Search Using Trie in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie data structure?

A Trie is a tree-like data structure that stores a dynamic set of strings, where each node represents a character. It is used to efficiently search for words or prefixes.

beginner

How does a Trie help in prefix search?

A Trie allows prefix search by following the path of characters from the root node down to the node representing the last character of the prefix. All words under this node share the prefix.

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 traverse one node per character in the prefix.

beginner

In a Trie node, what does the 'children' map represent?

The 'children' map stores links to child nodes, each corresponding to a character that can follow the current node's character in stored words.

beginner

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

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

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

A It allows searching prefixes in time proportional to prefix length

B It uses less memory than arrays

C It sorts words automatically

D It stores only unique words

A Trie lets you find prefixes by following nodes for each character, so search time depends only on prefix length.

In a Trie, what does each node typically represent?

A A number

B A whole word

C A character

D A prefix length

Each node in a Trie represents a single character in the stored strings.

If a prefix is not found in a Trie, what does that mean?

A The Trie is empty

B No word in the Trie starts with that prefix

C All words have that prefix

D The prefix is a complete word

If the prefix path does not exist, no stored word starts with that prefix.

What data structure is commonly used inside a Trie node to store children?

A Map or dictionary

B Stack

C Queue

D Linked list

A map or dictionary is used to link characters to child nodes efficiently.

What is the space complexity concern with Tries?

A They compress all words

B They use less memory than hash tables

C They store only one word

D They can use a lot of memory due to many nodes

Tries can consume a lot of memory because each character creates a node, especially with many words.

Explain how prefix search works using a Trie data structure.

Think about walking down the tree one character at a time.

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

Imagine each node as a letter box with links to next letters.