Tries Flashcards
(48 cards)
What is a trie?
A tree-like data structure used to store strings, where each node represents a character of the string.
What is another name for a trie?
Prefix tree.
What is the primary use of a trie?
To store and retrieve strings efficiently, especially for prefix-based queries.
What is a typical application of a trie?
Autocomplete, spell checking, and dictionary word searches.
What is the time complexity of searching a string in a trie?
O(m), where m is the length of the string.
What is the time complexity of inserting a string in a trie?
O(m), where m is the length of the string.
What is the time complexity of deleting a string from a trie?
O(m), where m is the length of the string.
What is the space complexity of a trie?
O(n * m), where n is the number of words and m is the average length.
What is stored at each node of a trie?
A character and optionally a flag indicating the end of a word.
What is the root node of a trie?
An empty node that serves as the starting point for all insertions and lookups.
How do you check if a word exists in a trie?
Traverse the trie following the characters; check if the last node is marked as end-of-word.
What is an end-of-word marker in a trie?
A boolean flag indicating that a complete word ends at that node.
How do you handle shared prefixes in a trie?
Nodes are shared among words that have the same prefix.
What happens if two words share a prefix in a trie?
They branch from the common prefix node.
What is the difference between a trie and a binary search tree?
Tries store data character-by-character in paths, while BSTs compare entire strings.
How do you insert a word into a trie?
Traverse or create nodes for each character and mark the final node as an end-of-word.
Can tries store numbers?
Yes, if digits are treated as characters.
Can tries store non-alphabetic characters?
Yes, if the trie is designed to handle them.
What is a compressed trie?
A trie where chains of single-child nodes are compressed into one node.
What is a ternary search trie?
A trie that uses a binary search tree structure at each node to reduce space.
What is a Patricia trie?
A compressed trie with binary branching used in networking and IP routing.
What is the main benefit of tries over hash tables?
Tries provide efficient prefix-based operations and are ordered.
How is a trie used in autocomplete systems?
By traversing to the node representing the prefix and exploring all descendant words.
What is the advantage of tries in dictionary word lookup?
O(m) time search and supports prefix-based queries.
