Binary Search Trees (BST) Quiz
40 comprehensive questions exploring binary search tree operations — with 16 code examples covering searching, insertion, deletion, and BST properties in this cpp quiz.
40 Questions
~80 minutes
1
Question 1
What is a binary search tree?
A
A binary tree where for each node, all elements in its left subtree are less than the node, and all elements in its right subtree are greater than the node, maintaining the binary search property throughout the tree
B
A tree with exactly two children per node
C
A tree where nodes are arranged randomly
D
A tree with no ordering requirements
2
Question 2
In a BST, where is the smallest element located?
text
BST property: left < root < right
Smallest: leftmost leafA
The leftmost node in the tree, reached by following left pointers from the root until reaching a leaf, representing the minimum value in the ordered structure
B
The root node
C
The rightmost node
D
Any leaf node
3
Question 3
What is the average time complexity for searching in a BST?
A
O(log n) for balanced BSTs, as each comparison eliminates half the remaining elements, following the binary search pattern with logarithmic depth
B
O(n)
C
O(1)
D
O(n log n)
4
Question 4
How does BST insertion maintain the binary search property?
text
Insert 5 into BST with root 3:
Compare 5 > 3, go right
Insert as right childA
By comparing the new value with nodes during traversal and placing it in the correct position where it belongs according to the BST ordering invariant
B
By placing new nodes randomly
C
By always inserting at the root
D
By inserting in level order
5
Question 5
What happens when you insert a duplicate value into a BST?
A
Depends on the implementation, as BSTs typically don't handle duplicates or handle them by placing them in left or right subtrees according to the chosen convention
B
Duplicates are always rejected
C
Duplicates replace existing nodes
D
Duplicates are stored in a separate structure
6
Question 6
In BST deletion, what is the most complex case?
text
Delete node with two children:
Find inorder successor
Replace node value
Delete successorA
Deleting a node with two children, requiring finding the inorder successor or predecessor and restructuring the tree while maintaining BST properties
B
Deleting a leaf node
C
Deleting a node with one child
D
Deleting the root node
7
Question 7
What is the inorder successor of a node in a BST?
A
The smallest node greater than the current node, found by going right once then left until leaf, or the rightmost ancestor if no right subtree exists
B
The largest node less than the current node
C
The parent node
D
Any child node
8
Question 8
How does BST search work?
cpp
bool search(Node* root, int key) {
if (!root) return false;
if (key == root->val) return true;
if (key < root->val) return search(root->left, key);
return search(root->right, key);
}A
By comparing the search key with node values and following left for smaller values or right for larger values, eliminating half the tree at each step in the average case
B
By visiting every node
C
By starting from leaf nodes
D
By using random traversal
9
Question 9
What is the worst-case time complexity for BST operations?
A
O(n) when the tree becomes skewed like a linked list, losing the balanced property and requiring linear time for search, insert, and delete operations
B
O(log n)
C
O(1)
D
O(n log n)
10
Question 10
In BST insertion, where is a new node placed when the tree is empty?
cpp
Empty tree: root = new Node(value);A
The new node becomes the root of the tree, establishing the first element in the BST structure and starting the ordered hierarchy
B
As a leaf in the left subtree
C
As a leaf in the right subtree
D
At a random position
11
Question 11
What is the BST invariant?
A
For every node, all values in left subtree are less than node value, and all values in right subtree are greater than node value, maintaining global ordering throughout the tree
B
All nodes have two children
C
The tree is balanced
D
No duplicate values allowed
12
Question 12
How does BST deletion handle a leaf node?
text
Delete leaf: simply remove it
No children to worry aboutA
Simply remove the leaf node and update the parent's pointer to null, as leaves have no children that need restructuring or reordering
B
Replace it with its inorder successor
C
Replace it with its parent
D
Cannot delete leaf nodes
13
Question 13
What is the inorder predecessor of a node in BST?
A
The largest node smaller than the current node, found by going left once then right until leaf, or the leftmost ancestor if no left subtree exists
B
The smallest node greater than the current node
C
The right child
D
Any ancestor
14
Question 14
In BST, how do you find the k-th smallest element?
text
Use inorder traversal with counter:
Keep count during inorder traversalA
Perform inorder traversal while maintaining a counter, stopping when the counter reaches k to find the k-th element in sorted order
B
Use level-order traversal
C
Search randomly
D
Cannot find k-th element efficiently
15
Question 15
What is the space complexity of BST operations?
A
O(n) for storing n elements in the tree nodes, with each operation using O(h) auxiliary space where h is the tree height for recursion or iteration
B
O(1)
C
O(log n)
D
O(n log n)
16
Question 16
How does BST insertion handle the case where the insertion point is found?
cpp
Node* insert(Node* root, int val) {
if (!root) return new Node(val);
if (val < root->val) root->left = insert(root->left, val);
else root->right = insert(root->right, val);
return root;
}A
Recursively traverse to the appropriate leaf position and create a new node, maintaining the BST property through ordered comparisons at each level
B
Replace existing nodes
C
Insert at root always
D
Insert randomly
17
Question 17
What is the advantage of BST over linear search?
A
Average O(log n) search time compared to O(n) linear search, providing significant performance improvement for large datasets through the ordered tree structure
B
Uses less memory
C
Easier to implement
D
Supports duplicate values better
18
Question 18
In BST deletion, how do you handle a node with one child?
text
Node has one child: replace with child
Parent points to child directlyA
Replace the node with its child and update the parent's pointer, maintaining BST properties since the child subtree satisfies the ordering requirements
B
Delete the child as well
C
Replace with inorder successor
D
Cannot delete nodes with children
19
Question 19
What happens to BST performance when insertions are in sorted order?
A
The tree becomes skewed into a linked list, degrading performance to O(n) for all operations due to the loss of balance in the tree structure
B
Performance improves
C
Performance remains O(log n)
D
The tree becomes perfectly balanced
20
Question 20
How do you validate if a binary tree is a BST?
text
Check recursively:
bool isBST(Node* root, int min, int max)A
Recursively check that each node's value is within valid range defined by its ancestors, ensuring left children are less than parent and right children are greater
B
Check if it's balanced
C
Check if all leaves are at same level
D
Check the number of nodes
21
Question 21
What is the relationship between BST and quicksort?
A
BST insertion order can create the same partitioning as quicksort, where the root becomes the pivot and subtrees represent partitioned arrays in the sorting process
B
They are completely unrelated
C
BST is faster than quicksort
D
Quicksort uses BST internally
22
Question 22
In BST, how do you find the floor of a given value?
text
Floor: largest value <= target
Traverse and track candidatesA
Traverse the tree while tracking the largest value that is less than or equal to the target, using BST properties to guide the search direction efficiently
B
Always return the root value
C
Use inorder traversal
D
Cannot find floor in BST
23
Question 23
What is the BST property violated in this tree?
text
5
/ \
3 7
/ \
2 6
6 > 5 but in left subtree - violation!A
The value 6 is in the left subtree of 5 but is greater than 5, violating the BST invariant that all left subtree values must be less than the root
B
The tree is not balanced
C
There are duplicate values
D
The tree has wrong height
24
Question 24
How does BST support range queries?
A
By traversing only relevant subtrees based on range bounds, pruning branches that cannot contain values in the desired range using the BST ordering property
B
By visiting all nodes
C
By using level-order traversal
D
Range queries are not efficient in BST
25
Question 25
What is the inorder traversal result for a BST?
text
BST inorder: always sorted ascending
Example: 2, 3, 5, 6, 7A
A sorted sequence in ascending order, as inorder traversal visits nodes in left-root-right pattern, which corresponds to increasing value order in a valid BST
B
A sorted sequence in descending order
C
A random order
D
The preorder sequence
26
Question 26
In BST deletion with two children, why use inorder successor?
A
The inorder successor is the smallest value greater than the node, ensuring it can replace the deleted node while maintaining BST properties in both left and right subtrees
B
It has no children
C
It is always a leaf
D
It is randomly chosen
27
Question 27
What is the best-case height for a BST with n nodes?
text
Perfect BST: height = floor(log2(n))A
Floor(log2(n)) when the tree is perfectly balanced, providing optimal height and logarithmic performance for all operations
B
n-1
C
1
D
n/2
28
Question 28
How does BST handle duplicate values in practice?
A
Implementation-dependent, with common approaches placing duplicates in left subtree, right subtree, or not allowing them at all, depending on the specific BST variant and use case requirements
B
Always rejects duplicates
C
Always replaces existing values
D
Stores duplicates in a separate list
29
Question 29
What is the amortized cost of BST operations?
text
Average case: O(log n)
Worst case: O(n)A
O(log n) average case for random insertions, but O(n) worst case when the tree becomes skewed, making the amortized analysis dependent on the insertion pattern
B
Always O(log n)
C
Always O(n)
D
O(1)
30
Question 30
In BST, how do you find all elements in a range [low, high]?
A
Traverse the tree and collect nodes where low ≤ node.value ≤ high, using BST properties to potentially skip irrelevant subtrees during the range search
B
Use inorder traversal only
C
Visit all nodes
D
Cannot perform range queries efficiently
31
Question 31
What is the significance of BST in algorithm design?
text
BST enables:
- Fast search O(log n)
- Ordered operations
- Range queriesA
Provides logarithmic-time search and ordered operations, serving as the foundation for more complex data structures and enabling efficient implementation of dictionaries and ordered sets
B
Is the fastest data structure
C
Uses the least memory
D
Is easiest to implement
32
Question 32
How does BST insertion differ from binary tree insertion?
A
BST insertion must maintain the ordering invariant by placing elements in specific positions based on comparisons, while binary tree insertion can place elements anywhere
B
They are identical
C
BST insertion is simpler
D
Binary tree insertion maintains order
33
Question 33
What is the ceiling of a value in BST?
text
Ceiling: smallest value >= target
Similar to floor but opposite directionA
The smallest value in the tree that is greater than or equal to the target, found by tracking candidates during BST traversal using the ordering properties
B
The largest value less than the target
C
The root value
D
Cannot find ceiling in BST
34
Question 34
In BST, what is the cost of finding the minimum element?
A
O(h) where h is the tree height, requiring traversal from root to leftmost leaf following left pointers in the worst case for skewed trees
B
O(1)
C
O(log n) always
D
O(n)
35
Question 35
How does BST support ordered iteration?
text
Inorder traversal gives sorted order:
for(auto val : bst) // sortedA
Through inorder traversal which visits nodes in ascending order, providing a natural way to iterate through elements in sorted sequence without additional sorting
B
Through level-order traversal
C
Through random access
D
BST doesn't support ordered iteration
36
Question 36
What is the impact of deletion on BST balance?
A
Deletion can create imbalances by removing nodes and potentially creating skewed structures, though the BST invariant is maintained, performance may degrade without rebalancing
B
Deletion always improves balance
C
Deletion has no impact on balance
D
Deletion always creates perfect balance
37
Question 37
In BST, how do you count nodes within a range?
text
Range count: traverse and count
Can be optimized with subtree sizesA
Traverse the tree counting nodes that fall within the range, or use augmented BSTs with subtree sizes for O(log n) range counting queries
B
Use inorder traversal only
C
Count all nodes
D
Cannot count ranges efficiently
38
Question 38
What makes BST different from hash tables?
A
BST maintains ordered data with logarithmic operations and supports range queries, while hash tables provide average O(1) access but no ordering or range operations
B
BST is always faster
C
Hash tables maintain order
D
They are identical in functionality
39
Question 39
How does BST handle the problem of sorted input insertions?
text
Sorted input creates skewed tree:
1, 2, 3, 4, 5 -> linked listA
Creates a skewed tree resembling a linked list, causing O(n) performance degradation that can be solved by using self-balancing BST variants like AVL or Red-Black trees
B
Creates a perfectly balanced tree
C
Rejects sorted inputs
D
Automatically rebalances
40
Question 40
Considering BST operations and their performance characteristics, which fundamental property makes BSTs valuable despite their worst-case performance issues in practice?
A
The combination of ordered data maintenance with average O(log n) operations and support for range queries, making BSTs suitable for applications requiring ordered access patterns despite worst-case vulnerabilities that can be mitigated through balancing techniques
B
Guaranteed O(log n) performance
C
Minimal memory usage
D
Simplicity of implementation only