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 (usually a boolean) in the last node of the inserted word to indicate that this path represents a complete word.
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 already stored, 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 the algorithm do?
✗ Incorrect
The algorithm reuses existing nodes to represent shared prefixes.
What flag is set to mark the end of a word in a Trie node?
✗ Incorrect
The isWordEnd flag marks that the path to this node forms a complete word.
What is the worst-case time complexity to insert a word of length n into 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 node.
You got /3 concepts.
Describe why Tries are efficient for prefix-based searches and how insertion supports this.
Focus on how shared prefixes reduce space and speed up searches.
You got /4 concepts.