Table of Contents
 Introduction
 Questions
 1. What is a Trie data structure? How does it work?
 2. What are the primary uses of a Trie? Can you provide some realworld examples where Tries are used?
 3. Can you describe the insertion process in a Trie? What is its time complexity?
 4. Can you describe the search process in a Trie? What is its time complexity?
 5. What are the advantages and disadvantages of using a Trie compared to other data structures like hash tables, trees, etc?
 6. What is a prefix in a Trie? How would you find all words in a Trie that have a common prefix?
 7. What is Trie’s space complexity? How can we optimize it?
 8. Can you explain the delete operation in a Trie?
 9. What is a Suffix Trie? How is it different from a standard Trie and what are its uses?
 10. What modifications can be done on a Trie to make it support advanced operations like sorting, priority queue, etc?
 Coding Questions
 1. Implement a Trie data structure in your preferred programming language. Include methods for insert, search, and startsWith.
 2. Given a list of strings, write a function that returns all strings with a given prefix using a Trie.
 3. Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cells, where “adjacent” cells are horizontally or vertically neighboring.
 4. Write a function to implement an autocomplete feature using Trie. The function should return all dictionary words that start with the provided input prefix.
 5. Implement a Trie data structure that supports insertion, deletion, and search operations.
 6. Given a string array, find the longest common prefix of all strings. Use a Trie to solve this problem.
 7. Implement a spell checker using a Trie. The spell checker should highlight words that are not present in a predefined dictionary.
 8. Given many words, words[i] has weight[i]. Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix). It will return the word with the given prefix and suffix with the maximum weight.
 9. Implement a Suffix Trie and include methods for constructing the suffix trie and for checking if a string is a suffix in the suffix trie.
 10. You are designing a search engine. In your search engine, you have stored all words of a dictionary in your database. Now, you want to design an algorithm that will be given an incomplete word (prefix), it will find the word in your database, and if it exists in your database, it will return true else false. Design this algorithm.
 MCQ Questions
 1. What is a Trie data structure?
 2. Which of the following operations can be performed efficiently on a Trie?
 3. What is the time complexity for searching a key in a Trie?
 4. In a Trie, each node represents:
 5. Which data structure is commonly used to implement the Trie?
 6. What is the space complexity of a Trie?
 7. Which of the following statements about Tries is true?
 8. In a Trie, how many children can a node have?
 9. Which of the following is not a common application of Tries?
 10. Which of the following operations is not typically supported by Tries?
 11. In a Trie, what does the leaf node represent?
 12. What is the main advantage of using a Trie over other data structures for string storage and retrieval?
 13. Which of the following is a drawback of using Tries?
 14. Which of the following is a common optimization technique used in Tries?
 15. What is the purpose of the “null” character in a Trie?
 16. Which of the following operations on a Trie can have a time complexity of O(N), where N is the total number of keys?
 17. Which data structure is commonly used to implement the child nodes in a Trie?
 18. In a Trie, how are the keys stored?
 19. Which of the following operations can be performed efficiently on a Trie?
 20. Which of the following statements about Tries is false?
Introduction
Trie interview questions often test your understanding of a data structure called a trie, which stands for “reTRIEval.” A trie is a treelike structure used to efficiently store and retrieve strings. It’s particularly useful for tasks like autocompletion and spellchecking. In these questions, you might be asked to implement a trie, perform operations on it, or solve problems using triebased approaches. Familiarizing yourself with trie operations, such as inserting, searching, and deleting nodes, will help you tackle these interview questions effectively. Remember, the key is to break down the problem into smaller steps and leverage the trie’s unique properties to optimize your solution.
Questions
1. What is a Trie data structure? How does it work?
A Trie (pronounced as “try”) data structure, also known as a prefix tree or digital tree, is a treelike data structure used to efficiently store a dynamic set of strings or keys. It is particularly useful for applications that involve searching for words or strings with common prefixes, such as in dictionary implementations or autocomplete systems.
Structure and Working of a Trie:
 Node Structure: Each node in the trie represents a single character of a string. Nodes are connected to form a tree, where the root node represents an empty string, and each path from the root to a node represents a string.
 Children and Links: Each node may have multiple child nodes, one for each possible character in the alphabet or set of characters. Each node contains links to its children, and these links represent the characters needed to traverse the trie from the root to a particular node.
 Word Completion: A node in the trie is marked as a wordcompletion node when it represents the end of a valid word. This helps distinguish complete words from prefixes.
 Searching: Searching for a specific word in the trie involves traversing the tree from the root, following the links corresponding to each character of the word. If the complete word exists in the trie, we will reach a wordcompletion node.
 Insertion: Inserting a new word into the trie involves starting from the root and traversing the tree based on the characters of the word. If a character does not have a corresponding child node, a new node is created and linked to its parent node.
 Deletion: Deleting a word from the trie involves finding the word in the trie and removing the wordcompletion marker. If the word is a prefix for other words, the relevant nodes are not deleted but remain in the trie.
Example:
Suppose we have the following set of words: “apple,” “app,” “banana,” and “bat.” A simplified illustration of a trie for these words would look like this:
(root)
/
a
/ \
p b
/ \
p a
/ \
l t
/ \ \
e p a
\
n
\
a
In this example, the trie efficiently stores the words “apple,” “app,” “banana,” and “bat,” with common prefixes like “app” and “ba.”
2. What are the primary uses of a Trie? Can you provide some realworld examples where Tries are used?
The primary uses of a Trie include:
 Autocomplete and word suggestion systems
 Spell checkers and dictionaries
 IP routing and network routing tables
 Searching for strings with common prefixes efficiently
 Storing and retrieving contact information in phonebooks
Realworld examples where Tries are used include:
 Search engines like Google, where autocomplete suggestions are provided as you type
 Word processing software for spell checking
 Network routers for IP address lookup and routing
 Contact lists in mobile phones for efficient search and retrieval
3. Can you describe the insertion process in a Trie? What is its time complexity?
The insertion process in a Trie involves adding a new word into the data structure. Each character of the word is sequentially inserted, creating a path from the root to the corresponding leaf node. If a node for a character doesn’t exist, it is created during the insertion process. The last node of the word is marked as a terminal node to indicate the completion of the word.
Example of inserting the word “apple” into an empty Trie:
Root

a

p

p

l

e (terminal node)
Time Complexity: The time complexity for inserting a word into a Trie is O(L), where L is the length of the word. This is because the insertion process involves traversing through each character of the word and adding it to the Trie, which takes constant time for each character.
4. Can you describe the search process in a Trie? What is its time complexity?
The search process in a Trie involves finding a specific word or checking if a given prefix exists in the Trie. Starting from the root, each character of the target word (or prefix) is sequentially searched by following the corresponding edges. If, at any point, a character is not found or the search reaches a null node, the word (or prefix) is not present in the Trie.
Example of searching for the word “apple” in a Trie:
Root

a

p

p

l

e (terminal node)
Searching for “apple” will return true, while searching for “app” (a valid prefix) will also return true.
Time Complexity: The time complexity for searching in a Trie is O(L), where L is the length of the target word or prefix. This is because the search process involves traversing through each character of the word or prefix, which takes constant time for each character.
5. What are the advantages and disadvantages of using a Trie compared to other data structures like hash tables, trees, etc?
Advantages of using a Trie:
 Efficient search and retrieval of strings with common prefixes
 Provides autocomplete functionality and efficient word suggestions
 Supports alphabetical ordering and range queries
 Can handle large datasets efficiently
 Wellsuited for tasks like spell checking and word processing applications
Disadvantages of using a Trie:
 Higher memory consumption compared to other data structures
 Slower for searching exact matches compared to hash tables
 Limited to storing strings and does not support generalpurpose data storage
 Can be more complex to implement and maintain compared to simpler data structures
6. What is a prefix in a Trie? How would you find all words in a Trie that have a common prefix?
A prefix in a Trie is a sequence of characters that appears at the beginning of one or more words stored in the Trie. For example, in the Trie below, “app” is a common prefix for both “apple” and “appetite”:
Root

a

p

p
/ \
l e (terminal node)
 
e t

i

t

e (terminal node)
To find all words in a Trie that have a common prefix, you can perform a traversal of the Trie starting from the node corresponding to the last character of the prefix. During this traversal, you can use DepthFirst Search (DFS) to explore all paths from the prefix node and collect the words encountered in the process.
Example code in C++ to find all words with a given prefix:
#include <iostream>
#include <vector>
using namespace std;
struct TrieNode {
bool isTerminal;
vector<TrieNode*> children;
TrieNode() : isTerminal(false), children(26, nullptr) {}
};
class Trie {
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* node = root;
for (char ch : word) {
int idx = ch  'a';
if (!node>children[idx])
node>children[idx] = new TrieNode();
node = node>children[idx];
}
node>isTerminal = true;
}
vector<string> findAllWithPrefix(string prefix) {
vector<string> result;
TrieNode* node = findPrefixNode(prefix);
if (node)
findAllWords(node, prefix, result);
return result;
}
private:
TrieNode* root;
TrieNode* findPrefixNode(string prefix) {
TrieNode* node = root;
for (char ch : prefix) {
int idx = ch  'a';
if (!node>children[idx])
return nullptr;
node = node>children[idx];
}
return node;
}
void findAllWords(TrieNode* node, string currentWord, vector<string>& result) {
if (node>isTerminal)
result.push_back(currentWord);
for (int i = 0; i < 26; i++) {
if (node>children[i]) {
char ch = 'a' + i;
findAllWords(node>children[i], currentWord + ch, result);
}
}
}
};
int main() {
Trie trie;
trie.insert("apple");
trie.insert("appetite");
trie.insert("bat");
trie.insert("ball");
string prefix = "app";
vector<string> wordsWithPrefix = trie.findAllWithPrefix(prefix);
cout << "Words with prefix '" << prefix << "': ";
for (const string& word : wordsWithPrefix)
cout << word << " ";
return 0;
}
Output for the given example Trie and prefix “app”:
Words with prefix 'app': apple appetite
7. What is Trie’s space complexity? How can we optimize it?
The space complexity of a Trie depends on the number of unique strings stored in it. In the worstcase scenario, where there are no common prefixes among the strings, the space complexity can be high. It is typically O(n * m), where n is the number of strings and m is the average length of the strings.
To optimize the space complexity of a Trie, some techniques can be employed:
 Implementing compressed tries, such as Patricia Tries or Ternary Search Tries, which reduce memory usage by storing common prefixes only once
 Using techniques like path compression or bitwise tries to further reduce memory usage
 Implementing adaptive or hybrid data structures that dynamically switch between different representations based on the data characteristics
8. Can you explain the delete operation in a Trie?
The delete operation in a Trie involves removing a word from the data structure. Deleting a word requires traversing the Trie to find the word and then marking the terminal node of the word as nonterminal (if it’s the only occurrence) or completely removing the nodes that are not shared with other words.
The deletion process depends on the following cases:
 The word to be deleted is not in the Trie: In this case, no changes are needed as the word is not present.
 The word to be deleted is a prefix of another word: Only mark the terminal node as nonterminal. The word is no longer accessible, but its prefix still exists in the Trie.
 The word to be deleted shares a prefix with another word: Traverse the Trie and remove nodes from the end of the word until encountering a shared node with another word.
 The word to be deleted is the only word sharing a prefix: Remove nodes starting from the root until the last node of the word.
Example of deleting the word “apple” from a Trie:
Root

a

p

p
/ \
l e (terminal node)
 
e t

i

t

e (terminal node)
After deleting “apple”:
Root

a

p
/ \
l e

e t

i

t

e (terminal node)
In the example above, “appetite” still exists in the Trie, and “app” is still a valid prefix.
9. What is a Suffix Trie? How is it different from a standard Trie and what are its uses?
A Suffix Trie, also known as a Suffix Tree, is a specialized type of Trie that is used to store all the suffixes of a given string. In a Suffix Trie, every path from the root to a leaf node represents a suffix of the original string. It allows for efficient pattern matching and substring searches in linear time.
The main difference between a Suffix Trie and a standard Trie is that a Suffix Trie is built specifically for storing and searching suffixes, while a standard Trie is a more generalpurpose data structure for storing and searching strings.
Some common uses of Suffix Tries include:
 Pattern matching and substring searches in DNA sequencing, text indexing, and search engines
 Longest common substring and longest repeated substring problems
 Construction of BurrowsWheeler Transform for data compression algorithms like bzip2
10. What modifications can be done on a Trie to make it support advanced operations like sorting, priority queue, etc?
To support advanced operations like sorting or priority queue, additional modifications can be made to a Trie, such as:
 Associating values or metadata with each node to store additional information like frequency, priority, or sorting keys
 Augmenting the Trie with additional data structures like heap or balanced trees to maintain the desired order or priority
 Implementing traversal algorithms that utilize the Trie structure to perform sorting or prioritybased operations efficiently
 Building specialized data structures like Triebased heaps or priority queues that leverage the Trie’s structure to achieve efficient operations
Coding Questions
1. Implement a Trie data structure in your preferred programming language. Include methods for insert, search, and startsWith.
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (!node.containsKey(c)) {
node.put(c, new TrieNode());
}
node = node.get(c);
}
node.setEnd();
}
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isEnd();
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
private TrieNode searchPrefix(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
if (node.containsKey(c)) {
node = node.get(c);
} else {
return null;
}
}
return node;
}
private static class TrieNode {
private TrieNode[] links;
private boolean isEnd;
public TrieNode() {
links = new TrieNode[26];
}
public boolean containsKey(char c) {
return links[c  'a'] != null;
}
public TrieNode get(char c) {
return links[c  'a'];
}
public void put(char c, TrieNode node) {
links[c  'a'] = node;
}
public boolean isEnd() {
return isEnd;
}
public void setEnd() {
isEnd = true;
}
}
}
2. Given a list of strings, write a function that returns all strings with a given prefix using a Trie.
public List<String> searchByPrefix(String prefix, Trie trie) {
List<String> result = new ArrayList<>();
Trie.TrieNode node = trie.searchPrefix(prefix);
if (node != null) {
dfs(node, prefix, result);
}
return result;
}
private void dfs(Trie.TrieNode node, String prefix, List<String> result) {
if (node.isEnd()) {
result.add(prefix);
}
for (char c = 'a'; c <= 'z'; c++) {
if (node.containsKey(c)) {
dfs(node.get(c), prefix + c, result);
}
}
}
3. Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cells, where “adjacent” cells are horizontally or vertically neighboring.
public List<String> findWords(char[][] board, String[] words) {
List<String> result = new ArrayList<>();
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dfs(board, i, j, "", trie, visited, result);
}
}
return result;
}
private void dfs(char[][] board, int i, int j, String currentWord, Trie trie, boolean[][] visited, List<String> result) {
if (i < 0  i >= board.length
 j < 0  j >= board[0].length  visited[i][j]) {
return;
}
currentWord += board[i][j];
if (!trie.startsWith(currentWord)) {
return;
}
if (trie.search(currentWord)) {
result.add(currentWord);
}
visited[i][j] = true;
dfs(board, i  1, j, currentWord, trie, visited, result);
dfs(board, i + 1, j, currentWord, trie, visited, result);
dfs(board, i, j  1, currentWord, trie, visited, result);
dfs(board, i, j + 1, currentWord, trie, visited, result);
visited[i][j] = false;
}
4. Write a function to implement an autocomplete feature using Trie. The function should return all dictionary words that start with the provided input prefix.
public List<String> autocomplete(String prefix, Trie trie) {
List<String> result = new ArrayList<>();
Trie.TrieNode node = trie.searchPrefix(prefix);
if (node != null) {
dfs(node, prefix, result);
}
return result;
}
private void dfs(Trie.TrieNode node, String prefix, List<String> result) {
if (node.isEnd()) {
result.add(prefix);
}
for (char c = 'a'; c <= 'z'; c++) {
if (node.containsKey(c)) {
dfs(node.get(c), prefix + c, result);
}
}
}
5. Implement a Trie data structure that supports insertion, deletion, and search operations.
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c  'a'] == null) {
node.children[c  'a'] = new TrieNode();
}
node = node.children[c  'a'];
}
node.isEndOfWord = true;
}
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isEndOfWord;
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
private TrieNode searchPrefix(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
if (node.children[c  'a'] == null) {
return null;
}
node = node.children[c  'a'];
}
return node;
}
class TrieNode {
TrieNode[] children;
boolean isEndOfWord;
public TrieNode() {
children = new TrieNode[26];
}
}
}
6. Given a string array, find the longest common prefix of all strings. Use a Trie to solve this problem.
public String longestCommonPrefix(String[] strs) {
Trie trie = new Trie();
for (String str : strs) {
trie.insert(str);
}
StringBuilder commonPrefix = new StringBuilder();
Trie.TrieNode node = trie.root;
while (node != null && !node.isEndOfWord && hasSingleChild(node)) {
node = node.children[node.children.length  1];
commonPrefix.append(node.val);
}
return commonPrefix.toString();
}
private boolean hasSingleChild(Trie.TrieNode node) {
int count = 0;
for (Trie.TrieNode child :
node.children) {
if (child != null) {
count++;
if (count > 1) {
return false;
}
}
}
return count == 1;
}
7. Implement a spell checker using a Trie. The spell checker should highlight words that are not present in a predefined dictionary.
public class SpellChecker {
Trie dictionary;
public SpellChecker(String[] words) {
dictionary = new Trie();
for (String word : words) {
dictionary.insert(word);
}
}
public List<String> checkSpelling(String sentence) {
List<String> misspelledWords = new ArrayList<>();
String[] words = sentence.split(" ");
for (String word : words) {
if (!dictionary.search(word.toLowerCase())) {
misspelledWords.add(word);
}
}
return misspelledWords;
}
}
8. Given many words, words[i] has weight[i]. Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix). It will return the word with the given prefix and suffix with the maximum weight.
class WordFilter {
Trie trie;
public WordFilter(String[] words, int[] weights) {
trie = new Trie();
for (int i = 0; i < words.length; i++) {
String word = words[i];
for (int j = 0; j <= word.length(); j++) {
String prefix = word.substring(0, j);
for (int k = 0; k <= word.length(); k++) {
String suffix = word.substring(k);
String key = suffix + "#" + prefix;
trie.insert(key, weights[i]);
}
}
}
}
public int f(String prefix, String suffix) {
String key = suffix + "#" + prefix;
return trie.search(key);
}
}
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word, int weight) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c  'a'] == null) {
node.children[c  'a'] = new TrieNode();
}
node = node.children[c  'a'];
node.weight = weight;
}
}
public int search(String word) {
TrieNode node = searchPrefix(word);
return node != null ? node.weight : 1;
}
private TrieNode searchPrefix(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
if (node.children[c  'a'] == null) {
return null;
}
node = node.children[c  'a'];
}
return node;
}
class TrieNode {
TrieNode[] children;
int weight;
public TrieNode() {
children = new TrieNode[26];
weight = 0;
}
}
}
9. Implement a Suffix Trie and include methods for constructing the suffix trie and for checking if a string is a suffix in the suffix trie.
class SuffixTrie {
SuffixTrieNode root;
public SuffixTrie(String word) {
root = new SuffixTrieNode();
for (int i = 0; i < word.length(); i++) {
insertSuffix(root, word.substring(i), i);
}
}
private void insertSuffix(SuffixTrieNode node, String suffix, int index) {
if (suffix.isEmpty()) {
node.isEndOfWord = true;
node.index = index;
return;
}
char c = suffix.charAt(0);
SuffixTrieNode child = node.children[c  'a'];
if (child == null) {
child = new SuffixTrieNode();
node.children[c  'a'] = child;
}
insertSuffix(child, suffix.substring(1), index);
}
public boolean isSuffix(String suffix) {
SuffixTrieNode node = searchSuffix(root, suffix);
return node != null && node.isEndOfWord;
}
private SuffixTrieNode searchSuffix(SuffixTrieNode node, String suffix) {
if (suffix.isEmpty()) {
return node;
}
char c = suffix.charAt(0);
SuffixTrieNode child = node.children[c  'a'];
if (child == null) {
return null;
}
return searchSuffix(child, suffix.substring(1));
}
class SuffixTrieNode {
SuffixTrieNode[] children;
boolean isEndOfWord;
int index;
public SuffixTrieNode() {
children = new SuffixTrieNode[26];
isEndOfWord = false;
index = 1;
}
}
}
10. You are designing a search engine. In your search engine, you have stored all words of a dictionary in your database. Now, you want to design an algorithm that will be given an incomplete word (prefix), it will find the word in your database, and if it exists in your database, it will return true else false. Design this algorithm.
public class SearchEngine {
Trie dictionary;
public SearchEngine(String[] words) {
dictionary = new Trie();
for (String word : words) {
dictionary.insert(word);
}
}
public boolean searchWord(String prefix) {
return dictionary.search(prefix);
}
}
MCQ Questions
1. What is a Trie data structure?
a) A type of binary tree
b) A type of hash table
c) A type of linked list
d) A type of treebased data structure
Answer: d) A type of treebased data structure
2. Which of the following operations can be performed efficiently on a Trie?
a) Insertion
b) Deletion
c) Search
d) All of the above
Answer: d) All of the above
3. What is the time complexity for searching a key in a Trie?
a) O(1)
b) O(log N)
c) O(N)
d) O(M), where M is the length of the key
Answer: d) O(M), where M is the length of the key
4. In a Trie, each node represents:
a) A character
b) A complete word
c) A prefix of a word
d) A leaf node
Answer: c) A prefix of a word
5. Which data structure is commonly used to implement the Trie?
a) Linked list
b) Stack
c) Array
d) Queue
Answer: c) Array
6. What is the space complexity of a Trie?
a) O(1)
b) O(log N)
c) O(N)
d) O(M), where M is the total number of characters in all the keys
Answer: d) O(M), where M is the total number of characters in all the keys
7. Which of the following statements about Tries is true?
a) Tries are only used for string matching
b) Tries are not suitable for large datasets
c) Tries can be used for autocomplete and spell checking
d) Tries cannot handle variablelength keys
Answer: c) Tries can be used for autocomplete and spell checking
8. In a Trie, how many children can a node have?
a) At most one child
b) At most two children
c) At most four children
d) Any number of children
Answer: d) Any number of children
9. Which of the following is not a common application of Tries?
a) Spell checking
b) IP routing
c) Autocomplete
d) Database indexing
Answer: b) IP routing
10. Which of the following operations is not typically supported by Tries?
a) Minimum key retrieval
b) Maximum key retrieval
c) Range queries
d) Union operation
Answer: d) Union operation
11. In a Trie, what does the leaf node represent?
a) A character
b) A complete word
c) A prefix of a word
d) A parent node
Answer: b) A complete word
12. What is the main advantage of using a Trie over other data structures for string storage and retrieval?
a) Constant time complexity for all operations
b) Efficient memory utilization
c) Builtin support for sorting
d) Easy implementation
Answer: b) Efficient memory utilization
13. Which of the following is a drawback of using Tries?
a) High memory usage for large datasets
b) Slow insertion and deletion operations
c) Limited support for different character encodings
d) Inefficient search performance
Answer: a) High memory usage for large datasets
14. Which of the following is a common optimization technique used in Tries?
a) Path compression
b) Hashing
c) Dynamic programming
d) Memoization
Answer: a) Path compression
15. What is the purpose of the “null” character in a Trie?
a) It represents the end of a word
b) It represents an empty node
c) It serves as a separator between keys
d) It is used for error handling
Answer: a) It represents the end of a word
16. Which of the following operations on a Trie can have a time complexity of O(N), where N is the total number of keys?
a) Insertion
b) Deletion
c) Search
d) None of the above
Answer: d) None of the above
17. Which data structure is commonly used to implement the child nodes in a Trie?
a) Linked list
b) Stack
c) Array
d) Queue
Answer: c) Array
18. In a Trie, how are the keys stored?
a) As individual characters
b) As concatenated strings
c) As binary strings
d) As integer values
Answer: a) As individual characters
19. Which of the following operations can be performed efficiently on a Trie?
a) Finding the kth smallest key
b) Finding the median key
c) Finding the maximum common prefix
d) Finding the highest frequency key
Answer: c) Finding the maximum common prefix
20. Which of the following statements about Tries is false?
a) Tries are a type of treebased data structure
b) Tries are commonly used for dictionary implementations
c) Tries can be used for efficient pattern matching
d) Tries can only store lowercase letters
Answer: d) Tries can only store lowercase letters