PRACTICE • LEARN • GROW
Trie & Advanced MCQs
Solve topic-wise placement questions and improve your skills.
Trie & Advanced Progress
0 of 35 completed
0%
Topic Track
You are viewing MCQs in preview mode. Log in to select options, submit answers, and track your progress.
Log In to Answer
1
What is a Trie (also known as a prefix tree) primarily used for?
A.
Storing numeric values for heap operations
B.
Efficient retrieval and prefix searching of strings over an alphabet
C.
Balancing binary search trees
D.
Sorting large files externally
Explanation & Key
Correct Answer:
2
What is the time complexity of searching for a word of length L in a Trie containing N words?
A.
O(N)
B.
O(L)
C.
O(N * L)
D.
O(log N)
Explanation & Key
Correct Answer:
3
What does each node in a standard English lowercase Alphabet Trie typically contain?
A.
An array or hash map of 26 child pointers and a boolean flag `isEndOfWord`
B.
A single integer key and two child pointers (left, right)
C.
A pointer to parent only
D.
The complete string value
Explanation & Key
Correct Answer:
4
What is the main advantage of a Trie over a Hash Table for string lookups?
A.
Trie uses less memory always
B.
Trie can perform prefix-based queries (e.g. `startsWith(prefix)`) and autocomplete in O(L) time without collisions
C.
Trie has O(1) worst-case time for any length string
D.
Tries do not require pointers
Explanation & Key
Correct Answer:
5
What is a major disadvantage of a standard array-based Trie implementation?
A.
Slow search speed
B.
High memory overhead due to null child pointers in sparse nodes
C.
Cannot store duplicate characters
D.
Does not support deletion
Explanation & Key
Correct Answer:
6
How can the memory consumption of a standard Trie be optimized for sparse branches?
A.
Using a Radix Tree (Compressed Trie / Patricia Tree)
B.
Using a single array of size 1000
C.
Converting the Trie into a linked list
D.
Removing the root node
Explanation & Key
Correct Answer:
7
What is the time complexity to insert a word of length L into a Trie?
A.
O(1)
B.
O(L)
C.
O(L^2)
D.
O(2^L)
Explanation & Key
Correct Answer:
8
What is a Bitwise / Binary Trie commonly used for in competitive programming?
A.
Finding Maximum XOR pair among an array of integers in O(32 * N) time
B.
Sorting floating point numbers
C.
Matrix multiplication
D.
Finding shortest path in a graph
Explanation & Key
Correct Answer:
9
In auto-complete search engines, how does a Trie find all words starting with prefix P?
A.
Traverse down to the node matching prefix P, then run DFS/BFS to collect all downstream words
B.
Scan all nodes from the root randomly
C.
Sort the entire trie array
D.
Hash the prefix and look up in a bucket
Explanation & Key
Correct Answer:
10
What is the root node of a Trie?
A.
Represents the empty string / null character and contains links to starting characters
B.
Contains the longest word in the dictionary
C.
Stores the total count of words only
D.
Is always a leaf node
Explanation & Key
Correct Answer:
11
When deleting a word from a Trie, when is it safe to physically free/delete a TrieNode?
A.
Whenever the word is found
B.
Only when the node has no children AND is not marked as the end of another word
C.
Immediately after setting `isEndOfWord = false`
D.
Never; nodes can never be removed from a Trie
Explanation & Key
Correct Answer:
12
What traversal of a Trie prints all stored strings in alphabetical (lexicographical) order?
A.
Preorder traversal visiting children in alphabetical order (a to z)
B.
Postorder traversal from z to a
C.
Reverse Breadth First Search
D.
Level order traversal
Explanation & Key
Correct Answer:
13
What data structure is often substituted for a fixed-size pointer array `children[26]` to save memory when words have diverse or Unicode characters?
A.
A Hash Map or balanced Binary Search Tree (std::map) per node
B.
A circular queue
C.
A doubly linked list of size 100
D.
A binary heap
Explanation & Key
Correct Answer:
14
What is a Suffix Trie?
A.
A Trie containing all prefixes of a single word
B.
A Trie built from all suffixes of a given string
C.
A Trie sorted in descending order
D.
A Trie with only leaf nodes
Explanation & Key
Correct Answer:
15
What is the time complexity to build a Suffix Tree of a string of length N using Ukkonen's Algorithm?
A.
O(N^2)
B.
O(N log N)
C.
O(N)
D.
O(N^3)
Explanation & Key
Correct Answer:
16
How can a Trie be used to solve the "Longest Common Prefix" (LCP) problem among N strings?
A.
Insert all strings; traverse from the root as long as each node has exactly one child and isEndOfWord is false
B.
Find the height of the Trie
C.
Count total nodes in the Trie
D.
Reverse all strings and delete the root
Explanation & Key
Correct Answer:
17
In the LeetCode problem "Word Search II" (finding all dictionary words present on a 2D Boggle grid), why is a Trie used?
A.
It allows pruning DFS grid searches early when the current path does not match any prefix in the dictionary
B.
It avoids grid boundaries
C.
It replaces the need for 2D visited arrays
D.
It rotates the board automatically
Explanation & Key
Correct Answer:
18
What is an Aho-Corasick automaton?
A.
A Trie augmented with failure transitions (suffix links) to find all occurrences of multiple dictionary patterns in a text in linear time
B.
A hardware accelerator for Trie operations
C.
A sorting algorithm for words
D.
A binary search tree variant
Explanation & Key
Correct Answer:
19
Can a Trie be used to store integer keys?
A.
No, Tries only accept English letters
B.
Yes, by treating the binary bit representation (0s and 1s) as a 2-character alphabet
C.
Only if integers are converted to Roman numerals
D.
Only for numbers less than 10
Explanation & Key
Correct Answer:
20
What is the auxiliary space complexity of storing N strings of average length L in a basic Trie in the worst case?
A.
O(N)
B.
O(N * L * Alphabet_Size)
C.
O(1)
D.
O(log(N * L))
Explanation & Key
Correct Answer:
21
In a standard Trie storing strings over an alphabet of size Sigma, what is the maximum number of outgoing edges from any single node?
A.
2
B.
Sigma (e.g. 26 for lowercase English letters)
C.
n (number of words in dictionary)
D.
Unlimited
Explanation & Key
Correct Answer:
22
What is the worst-case space complexity of a Trie storing N words of maximum length L over an alphabet of size Sigma?
A.
O(N * L * Sigma)
B.
O(N + L)
C.
O(Sigma^L)
D.
O(N * Sigma)
Explanation & Key
Correct Answer:
23
How can memory consumption in a standard Trie be reduced when handling sparse alphabets (e.g. Unicode)?
A.
Replace fixed-size child pointer arrays with a Hash Map or balanced BST at each node
B.
Delete the root node
C.
Limit word length to 4 characters
D.
Store characters in a global array
Explanation & Key
Correct Answer:
24
What is a Compressed Trie (Radix Tree / Patricia Trie)?
A.
A trie that compresses node text using gzip
B.
A trie where every internal node with only one child is merged with its child, labeling edges with substrings instead of single characters
C.
A binary tree storing ASCII values
D.
A trie that discards leaf nodes
Explanation & Key
Correct Answer:
25
How is a Bitwise Trie (Binary Trie) utilized to solve the "Maximum XOR of Two Numbers in an Array" problem in O(32 * n) time?
A.
By inserting binary 32-bit representations and greedily traversing the opposite bit at each level to maximize XOR
B.
By sorting the array and XORing adjacent elements
C.
By computing prefix XORs with a hash map
D.
By converting numbers to strings and using KMP
Explanation & Key
Correct Answer:
26
What is the time complexity of deleting a word of length L from a Trie?
A.
O(L) using a post-order traversal to prune nodes with no remaining children
B.
O(N * L)
C.
O(1)
D.
O(L^2)
Explanation & Key
Correct Answer:
27
In a Trie supporting wildcard search (e.g., '.' matches any character), what search strategy is used when encountering a '.'?
A.
Return false immediately
B.
Recursively branch DFS across all non-null child pointers at the current node
C.
Skip the character without moving pointers
D.
Only check the first child pointer
Explanation & Key
Correct Answer:
28
What is the primary advantage of a Trie over a Hash Map for prefix-based queries?
A.
Trie uses less total memory for single words
B.
Trie can find all words with a given prefix in O(prefix_length + k) without scanning unrelated entries
C.
Trie has O(1) worst-case lookup for arbitrary keys
D.
Trie does not require pointers
Explanation & Key
Correct Answer:
29
How do you check if a word W of length L exists in a Trie?
A.
Traverse root to L; check if all child pointers exist AND the terminating node has isEndOfWord == true
B.
Count the number of nodes in the Trie
C.
Compare W with the root value
D.
Traverse leaves to root
Explanation & Key
Correct Answer:
30
What is a Suffix Tree?
A.
A Trie containing all suffixes of a given text string
B.
A binary tree of prefixes
C.
A linked list of string suffixes
D.
A heap of character frequencies
Explanation & Key
Correct Answer:
31
In a Trie implementation of an autocomplete system, how can we return the Top-K most frequent words for a prefix in O(1) time after locating the prefix?
A.
Sort the entire trie on each keystroke
B.
Pre-store a precomputed list of the top-K word suggestions directly inside each TrieNode during insertion
C.
Run BFS across all million nodes
D.
Use a random number generator
Explanation & Key
Correct Answer:
32
Can a Trie be used to sort an array of strings in lexicographical (alphabetical) order?
A.
Yes, inserting all strings into a Trie and performing a Pre-order traversal yields strictly alphabetical order
B.
No, Tries cannot maintain sorted order
C.
Only if all strings have equal length
D.
Only using post-order traversal
Explanation & Key
Correct Answer:
33
What is the root node's value in a standard Trie?
A.
The character 'a'
B.
It represents the empty string prefix and does not store a character value
C.
The length of the dictionary
D.
NULL pointer
Explanation & Key
Correct Answer:
34
In the Word Break problem, how does a Trie optimize the Dynamic Programming transition?
A.
It allows checking whether substrings s[i...j] exist in the dictionary by walking the Trie rather than performing repeated hash table lookups
B.
It eliminates the need for dynamic programming completely
C.
It sorts the dictionary words by length
D.
It converts string comparisons to integer arithmetic
Explanation & Key
Correct Answer:
35
In a Trie containing N words, what is the time complexity of the `startsWith(prefix)` operation for a prefix of length P?
A.
O(P)
B.
O(N * P)
C.
O(log N)
D.
O(P * log 26)
Explanation & Key
Correct Answer:
Question Palette
Answered
Current
Not Attempted
Wrong
