Prefix Search Using Trie in DSA Javascript - 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. It allows fast retrieval of words by their prefixes.

beginner

How does a Trie help in prefix search?

A Trie stores words by their characters in a tree. Searching for a prefix means following the path of characters in the Trie. If the path exists, all words below that 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 only traverse the Trie nodes corresponding to the prefix characters.

beginner

In a Trie node, what does each child represent?

Each child represents a possible next character in the stored words. For example, if the node has a child for 'a', it means some word continues with 'a' from this point.

intermediate

What is the main difference between a Trie and a Hash Map for prefix search?

A Trie supports efficient prefix search by structure, allowing retrieval of all words with a given prefix. A Hash Map does not support prefix search efficiently because it hashes whole keys, not prefixes.

What does each node in a Trie typically store?

A Only a number

B A character and links to child nodes

C A full word string

D A hash of the word

Each Trie node stores a character and links to child nodes representing next characters.

What is the first step to search for a prefix in a Trie?

A Traverse nodes following prefix characters

B Hash the prefix

C Sort all words

D Check the last character only

Searching a prefix means following the path of prefix characters in the Trie.

If a prefix path does not exist in a Trie, what does it mean?

A The prefix is a full word

B All words have that prefix

C The Trie is empty

D No words with that prefix exist

If the path for prefix characters is missing, no stored word has that prefix.

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

A Fast prefix lookup in O(m) time

B Uses less memory than arrays

C Stores numbers efficiently

D Hashes words for quick access

Trie allows prefix search in time proportional to prefix length, which is efficient.

Which of these is NOT true about Tries?

A They can store words sharing prefixes efficiently

B They support prefix search easily

C They hash words for quick lookup

D Each node can have multiple children

Tries do not use hashing; they use tree structure for storing characters.

Explain how a Trie is used to find all words starting with a given prefix.

Think about following characters step-by-step and then exploring below.

Describe the structure of a Trie node and how it supports prefix search.

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