Word Search in 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 of words.

beginner

How does a Trie help in word search?

A Trie allows fast prefix-based search by traversing nodes corresponding to each character of the word. If traversal reaches the end of the word and the node marks the end of a word, the word exists in the Trie.

beginner

What does the 'end of word' marker in a Trie node signify?

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

intermediate

In TypeScript, how do you represent children nodes in a Trie node?

Children nodes are often represented as a Map or an object with keys as characters and values as TrieNode references.

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 you traverse one node per character.

What does each node in a Trie represent?

A A character of a word

B A whole word

C A number

D A sentence

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

How do you know if a word exists in a Trie after traversal?

A If the first node is not null

B If the last node visited marks the end of a word

C If the Trie has more than one node

D If the word length is greater than zero

A word exists if the last node in traversal has an end-of-word marker.

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

A Map<string, TrieNode>

B Array<number>

C Set<string>

D Boolean

A Map is used to map characters to child nodes.

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

A Sorts words automatically

B Uses less memory than arrays

C Stores numbers efficiently

D Fast prefix-based search

Trie allows fast search by prefixes, making word search efficient.

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

A O(m^2)

B O(log m)

C O(m)

D O(1)

Searching requires checking each character once, so O(m).

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

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

Describe the structure of a Trie node used for word search.

Focus on what each node holds to help find words.