Tries Flashcards
Learn (10 cards)
How do you insert a word into a trie?
Add nodes for each character and mark the end of the word.
How do you mark the end of a word in a trie?
Use a special flag or indicator at the final character node.
What does startsWith return if a word with that prefix is in the trie?
True, because the prefix exists in at least one word.
How do you search for a word in a trie?
Follow character by character down the trie and check for word end.
Why are trie operations O(m)?
m is the length of the word or prefix, and you visit one node per letter.
How do you count how many words pass through a node in a trie?
Add a counter to each node and increment it during word insertions.
How do you delete a word from a trie?
Traverse the word, unmark the end, and remove unused nodes.
What are tries commonly used for?
- Autocomplete
- Spell-checking
- Fast prefix matching
If a trie has ‘CAT’ and ‘CAR’, how do you insert ‘CAN’?
Reuse the common prefix ‘CA’, then add a new node for ‘N’.
How do you build autocomplete suggestions from a prefix in a trie?
Traverse to the end of the prefix, then explore all paths below it to collect full words.
