Q.1 What is the key property of a Binary Search Tree (BST)?
All left child nodes are greater than the parent node
All right child nodes are less than the parent node
Left child nodes are less and right child nodes are greater than the parent node
All nodes have either 0 or 2 children
Explanation - In a BST, the left subtree contains nodes with keys smaller than the root, and the right subtree contains nodes with keys larger than the root.
Correct answer is: Left child nodes are less and right child nodes are greater than the parent node
Q.2 What is the time complexity of searching in a balanced BST?
O(n)
O(log n)
O(n log n)
O(1)
Explanation - In a balanced BST, each comparison allows us to skip half of the remaining tree, leading to a logarithmic time complexity.
Correct answer is: O(log n)
Q.3 Which traversal method of a BST gives nodes in ascending order?
Pre-order
In-order
Post-order
Level-order
Explanation - In-order traversal of a BST visits nodes in the left subtree first, then the root, and finally the right subtree, resulting in sorted order.
Correct answer is: In-order
Q.4 What is the worst-case time complexity for inserting a node in a BST?
O(n)
O(log n)
O(n log n)
O(1)
Explanation - In the worst case (when the tree degenerates into a linked list), insertion requires traversal of all nodes, resulting in O(n) time.
Correct answer is: O(n)
Q.5 If a BST has n nodes, what is the maximum height of the tree?
n
log n
n/2
sqrt(n)
Explanation - In the worst case (unbalanced tree), the BST can behave like a linked list with height equal to the number of nodes.
Correct answer is: n
Q.6 Which of the following is true about a BST?
Duplicates are always allowed on the left
Duplicates are always allowed on the right
BSTs cannot have duplicate keys
Duplicate placement depends on implementation
Explanation - BSTs may handle duplicates differently depending on the implementation, either left, right, or not allowing duplicates.
Correct answer is: Duplicate placement depends on implementation
Q.7 Which operation is generally used to remove a node with two children in a BST?
Replace with in-order predecessor or successor
Replace with left child
Replace with right child
Delete without replacement
Explanation - To maintain BST properties, a node with two children is replaced by either its in-order predecessor (max of left subtree) or successor (min of right subtree).
Correct answer is: Replace with in-order predecessor or successor
Q.8 What is the average height of a BST with n nodes?
O(log n)
O(n)
O(sqrt(n))
O(1)
Explanation - For a randomly built BST, the expected height is proportional to log n, giving efficient average-case operations.
Correct answer is: O(log n)
Q.9 Which of the following is NOT a valid BST traversal?
In-order
Pre-order
Post-order
Random-order
Explanation - BST traversal must follow a systematic order such as in-order, pre-order, post-order, or level-order. Random-order is not standard.
Correct answer is: Random-order
Q.10 In a BST, what is the in-order predecessor of a node?
Smallest node in the right subtree
Largest node in the left subtree
Immediate parent node
Root node
Explanation - The in-order predecessor of a node is the maximum value node in its left subtree.
Correct answer is: Largest node in the left subtree
Q.11 Which traversal is most suitable for copying a BST?
Pre-order
In-order
Post-order
Level-order
Explanation - Pre-order traversal visits the root first, allowing the tree to be reconstructed in the same shape in another location.
Correct answer is: Pre-order
Q.12 What is the time complexity to find the minimum value in a BST?
O(1)
O(log n) for balanced, O(n) for unbalanced
O(n log n)
O(n^2)
Explanation - Minimum value is the leftmost node. Traversal depends on tree height: log n for balanced, n for unbalanced BST.
Correct answer is: O(log n) for balanced, O(n) for unbalanced
Q.13 Which data structure is typically used to implement BST iteratively?
Queue
Stack
Linked List
Hash Table
Explanation - A stack is used to simulate the recursion stack when performing iterative traversals such as in-order or pre-order.
Correct answer is: Stack
Q.14 Which of the following statements is correct?
All BSTs are binary trees, but not all binary trees are BSTs
All binary trees are BSTs
BSTs must be full binary trees
BSTs must be complete binary trees
Explanation - A BST is a binary tree with additional ordering constraints; not all binary trees satisfy BST properties.
Correct answer is: All BSTs are binary trees, but not all binary trees are BSTs
Q.15 How many children can a BST node have?
0 only
1 only
0, 1, or 2
Exactly 2
Explanation - A BST node can have no child, one child, or two children according to the tree structure.
Correct answer is: 0, 1, or 2
Q.16 Which traversal is best to delete a BST safely without losing nodes?
Pre-order
In-order
Post-order
Level-order
Explanation - Post-order ensures child nodes are deleted before their parent nodes, preventing dangling references.
Correct answer is: Post-order
Q.17 In a BST, the rightmost node represents:
Minimum value
Maximum value
Root value
Average value
Explanation - The rightmost node has the largest key in a BST as all right children are greater than their parents.
Correct answer is: Maximum value
Q.18 Which of these is a correct property of a balanced BST?
Height of left and right subtrees differ by at most 1
All leaf nodes are at same depth
Left subtree is full, right subtree is empty
It must be a complete binary tree
Explanation - A balanced BST ensures logarithmic height by keeping subtree heights within 1 of each other.
Correct answer is: Height of left and right subtrees differ by at most 1
Q.19 Which type of BST is self-balancing?
AVL Tree
Simple BST
Linked List
Heap
Explanation - AVL Trees maintain balance automatically after insertions and deletions, ensuring O(log n) operations.
Correct answer is: AVL Tree
Q.20 Which operation may cause rebalancing in an AVL tree?
Insertion
Search
Traversal
Finding minimum
Explanation - Insertions (or deletions) may unbalance the tree, requiring rotations to maintain AVL balance property.
Correct answer is: Insertion
Q.21 What is the in-order successor of a node in a BST?
Smallest node in the right subtree
Largest node in the left subtree
Root node
Immediate parent node
Explanation - The in-order successor is the node with the smallest key greater than the given node, located in its right subtree.
Correct answer is: Smallest node in the right subtree
Q.22 Which of the following is true about deleting a leaf node in a BST?
Requires replacing it with its child
Requires rotations
Can be removed directly
Cannot be deleted
Explanation - A leaf node has no children, so it can be removed without affecting the BST structure.
Correct answer is: Can be removed directly
Q.23 What is the space complexity of a recursive BST traversal?
O(1)
O(h) where h is the tree height
O(n log n)
O(n^2)
Explanation - Recursive traversal uses the call stack proportional to the height of the tree, which is O(log n) for balanced and O(n) for unbalanced BST.
Correct answer is: O(h) where h is the tree height
Q.24 What does a degenerate BST resemble?
Linked list
Heap
Balanced tree
Complete tree
Explanation - A degenerate BST occurs when each node has only one child, effectively forming a linked list.
Correct answer is: Linked list
Q.25 Which of the following is a balanced BST?
AVL Tree
Linked List
Unbalanced BST
Heap
Explanation - AVL Trees automatically maintain balance after insertions and deletions, keeping height logarithmic.
Correct answer is: AVL Tree