Q.1 What is the primary property of a Binary Search Tree (BST)?
Every node has exactly two children
Left child is smaller, right child is larger
All nodes have equal values
It is always balanced
Explanation - In a BST, for any node, the left child contains smaller values, and the right child contains larger values than the parent.
Correct answer is: Left child is smaller, right child is larger
Q.2 What is the average time complexity of searching in a Binary Search Tree?
O(1)
O(n)
O(log n)
O(n log n)
Explanation - In a balanced BST, searching takes O(log n) time because the search space halves at each step.
Correct answer is: O(log n)
Q.3 In the worst case, the time complexity of search in a Binary Search Tree is:
O(log n)
O(n)
O(1)
O(n^2)
Explanation - If the BST is skewed (like a linked list), search may take O(n) time.
Correct answer is: O(n)
Q.4 Which traversal of a BST gives nodes in sorted order?
Preorder
Inorder
Postorder
Level order
Explanation - Inorder traversal of a BST produces sorted values because it visits nodes in increasing order.
Correct answer is: Inorder
Q.5 What is the space complexity of recursive search in a BST?
O(1)
O(n)
O(log n)
O(n log n)
Explanation - The recursion stack depth in a balanced BST is O(log n). In the worst case (skewed), it can be O(n).
Correct answer is: O(log n)
Q.6 What happens if duplicate elements are inserted into a standard BST?
Duplicates are ignored
Duplicates go to the left
Duplicates go to the right
It depends on the implementation
Explanation - Standard BST does not define how to handle duplicates. Implementations may place them consistently left or right or disallow them.
Correct answer is: It depends on the implementation
Q.7 The height of a balanced BST with n nodes is approximately:
log₂(n)
n
√n
n log n
Explanation - Balanced BSTs minimize height to about log₂(n).
Correct answer is: log₂(n)
Q.8 Which divide and conquer principle is applied in BST operations?
Split into halves at each decision
Always use linear search
Divide into random subtrees
No divide and conquer principle
Explanation - BST divides the search space into two halves (left and right subtree) at each step.
Correct answer is: Split into halves at each decision
Q.9 What is the time complexity to find the minimum element in a BST?
O(1)
O(log n)
O(n)
O(n log n)
Explanation - To find the minimum, we traverse left until NULL, where h is the tree height (O(log n) for balanced, O(n) for skewed).
Correct answer is: O(n)
Q.10 Which of the following is NOT an application of BST?
Searching
Sorting
Symbol table implementation
Matrix multiplication
Explanation - BSTs are not used for matrix multiplication but are used for searching, sorting, and symbol tables.
Correct answer is: Matrix multiplication
Q.11 Insertion in a BST has worst-case complexity:
O(log n)
O(1)
O(n)
O(n log n)
Explanation - In a skewed BST, insertion may traverse all nodes, giving O(n).
Correct answer is: O(n)
Q.12 Which node in a BST has the largest value?
Root node
Leftmost node
Rightmost node
Middle node
Explanation - In a BST, the rightmost node always contains the largest value.
Correct answer is: Rightmost node
Q.13 Which operation in a BST may require restructuring or deletion of two nodes?
Insertion
Search
Deletion
Traversal
Explanation - Deleting a node with two children requires replacing it with its inorder successor or predecessor.
Correct answer is: Deletion
Q.14 How is the inorder successor of a node in BST defined?
Largest value smaller than the node
Smallest value larger than the node
Always root
Always left child
Explanation - Inorder successor is the smallest node greater than the given node, found in the right subtree.
Correct answer is: Smallest value larger than the node
Q.15 What is the best-case time complexity for searching in BST?
O(1)
O(log n)
O(n)
O(n log n)
Explanation - If the key matches the root, search completes in O(1).
Correct answer is: O(1)
Q.16 Which of the following traversals is NOT depth-first?
Preorder
Inorder
Postorder
Level order
Explanation - Level order traversal is breadth-first, not depth-first.
Correct answer is: Level order
Q.17 What is the parent of the inorder successor of a node with right child?
The node itself
Leftmost node of right subtree
Right child
Root
Explanation - The inorder successor is found in the right subtree, making the node itself the parent of the successor.
Correct answer is: The node itself
Q.18 A perfectly balanced BST with 7 nodes has a height of:
2
3
4
7
Explanation - Height is log₂(n) rounded down. For 7 nodes, height = 2 (root at level 0).
Correct answer is: 2
Q.19 Which data structure is used to implement recursion in BST operations?
Queue
Stack
Array
Heap
Explanation - Recursion uses the call stack to store intermediate states.
Correct answer is: Stack
Q.20 What is the average number of comparisons to search in a BST with n nodes?
O(1)
O(log n)
O(n)
O(n log n)
Explanation - On average, a balanced BST reduces comparisons to O(log n).
Correct answer is: O(log n)
Q.21 Which condition makes a BST inefficient?
Balanced structure
Skewed structure
Equal distribution
Duplicate handling
Explanation - A skewed BST behaves like a linked list, degrading search to O(n).
Correct answer is: Skewed structure
Q.22 In a BST, what is the left child’s relationship to the parent?
Greater
Smaller
Equal
Random
Explanation - Left child always stores values smaller than parent in a BST.
Correct answer is: Smaller
Q.23 What is the inorder predecessor of a node?
Largest smaller value
Smallest larger value
Root
Rightmost leaf
Explanation - The inorder predecessor is the largest value smaller than the given node, usually in the left subtree.
Correct answer is: Largest smaller value
Q.24 If a BST has only right children, what is its height with n nodes?
O(1)
O(log n)
O(n)
O(n log n)
Explanation - If only right children exist, the tree is skewed and height = n.
Correct answer is: O(n)
Q.25 Which of the following operations is fastest in BST on average?
Search
Insert
Delete
All have same average case
Explanation - On average, search, insert, and delete all take O(log n) in a balanced BST.
Correct answer is: All have same average case