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 down the tree represent words.
Click to reveal answer
beginner
What does the insert operation do in a Trie?
The insert operation adds a word to the Trie by creating nodes for each character if they don't exist and marking the end of the word.
Click to reveal answer
beginner
In Trie insertion, what does marking the end of a word mean?
It means setting a flag (like isEndOfWord) in the last node of the inserted word to indicate that a complete word ends there.
Click to reveal answer
intermediate
Why do we create new nodes only if the character path does not exist during insertion?
Because existing nodes represent prefixes of other words, so we reuse them to save space and avoid duplication.
Click to reveal answer
intermediate
What is the time complexity of inserting a word of length n into a Trie?
The time complexity is O(n), where n is the length of the word, because we process each character once.
Click to reveal answer
What does each node in a Trie typically represent?
✗ Incorrect
Each node in a Trie represents a single character of a word.
During insertion, if a character node already exists, what should we do?
✗ Incorrect
We reuse existing nodes to represent shared prefixes and save space.
What flag is commonly used to mark the end of a word in a Trie node?
✗ Incorrect
The flag is commonly named isEndOfWord to indicate the end of a word.
What is the worst-case time complexity to insert a word of length n in a Trie?
✗ Incorrect
Insertion requires processing each character once, so O(n).
If you insert the words 'cat' and 'car' into a Trie, how many nodes will be shared?
✗ Incorrect
The nodes for 'c' and 'a' are shared, so 2 nodes.
Explain step-by-step how to insert the word 'dog' into an empty Trie.
Think about creating nodes for each character and marking the last one.
You got /5 concepts.
Describe why Tries are efficient for prefix-based searches and how insertion supports this.
Focus on shared nodes and marking word ends.
You got /5 concepts.