Word Search in 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. Each node represents a character, and paths from the root to leaves represent words.

beginner

How does a Trie help in word search?

A Trie allows fast word search by following the path of characters from the root node. If the path for all characters of a word exists and ends at a node marked as a word end, the word is found.

beginner

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

The 'isEndOfWord' flag marks that the path from the root to this node forms a complete word stored in the Trie.

intermediate

Explain the steps to search a word in a Trie.

Start at the root node. For each character in the word, check if a child node exists for that character. If not, the word is not in the Trie. If all characters are found, check if the last node's 'isEndOfWord' is true to confirm the word exists.

intermediate

Why is Trie more efficient than a list for searching words?

Trie reduces search time by sharing common prefixes among words, allowing search in O(m) time where m is the word length, instead of O(n) where n is the number of words in a list.

What does each node in a Trie represent?

A A whole word

B A sentence

C A number

D A character of a word

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

What indicates that a node marks the end of a word in a Trie?

A A boolean flag like 'isEndOfWord'

B The node has no children

C A special child node

D The node stores the word

The 'isEndOfWord' boolean flag marks the end of a word in a Trie node.

If a character path is missing in the Trie during search, what does it mean?

A The word does not exist

B The word exists

C The Trie is empty

D The word is a prefix

Missing character path means the word is not stored in the Trie.

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

A O(m * n)

B O(n)

C O(m)

D O(log n)

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

Which of these is a benefit of using a Trie for word search?

A Uses less memory than arrays

B Shares common prefixes to speed up search

C Stores words in sorted order automatically

D Allows searching numbers only

Trie shares common prefixes among words, making search faster.

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 searching words compared to lists.

Consider how common parts of words are stored once.