BST Basics and Operations MCQs: 12 Solved Questions with Explanations

BST questions often look like definition recall, but the answer usually depends on maintaining an allowable range during insertion, search or deletion. For each question, identify the allowable range before checking the explanation. The set moves from the ordering invariant through insertion, search, deletion, height and shape counting.

Use the Coding & DSA courses for broader study. Sketch the running range beside every search path.

Fix the BST invariant before attempting the questions

Keys 50, 30, 70, 20, 40, 60, 80 produce root 50; children 30 and 70; 20 and 40 under 30; 60 and 80 under 70. At each node, every left-subtree value is smaller and every right-subtree value greater.

The invariant controls all operations. Search 40 via 50 -> 30 -> 40. Insert 65 via 50 -> 70 -> 60, attaching it as 60.right. Inorder is 20, 30, 40, 50, 60, 70, 80. If shape and order still blur, revise the binary trees and binary search trees guide.

Definition, ordering, and root-subtree counts

Question 1

CoCubes 2023.

What is a Binary Search Tree (BST)?

• A. A tree in which each node has exactly two children

• B. A binary tree in which for each node, value of all the nodes in left sub tree is lesser and value of all nodes in right subtree is greater

• C. A tree in which every node has at most two children, and all children nodes are leaf nodes

• D. None of the above

Answer: B. At root 50, {20, 30, 40} is smaller and {60, 70, 80} is greater; the test repeats at 30 and 70. The trap is treating “binary” as an ordering rule or a demand for exactly two children. It only limits child count. Practice this question.

Question 2

BPSC 2024.

In a binary search tree, which subtree of a node contains elements that are greater than the node’s value?

• A. Left subtree

• B. Right subtree

• C. Both subtrees

• D. More than one of the above

• E. None of the above

Answer: B. Right subtree. At node 30, 40 > 30 puts 40 right; 20 < 30 puts 20 left. The rule covers the whole subtree. The trap is accepting a deeper value that passes its parent comparison but violates an earlier ancestor's bound. Practice this question.

Question 3

GATE 1996.

A binary search tree is generated by inserting in order the following integers:

   50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24

The number of nodes in the left subtree and right subtree of the root respectively is

• A. (4, 7)

• B. (7, 4)

• C. (8, 3)

• D. (3, 8)

Answer: B. (7, 4). Root 50 splits every later key. Smaller: 15, 5, 20, 3, 8, 37, 24. Larger: 62, 58, 91, 60. The trap is counting the root or thinking insertion order moves a key across 50. No full tree is needed. Practice this question.

Insertion depth, inorder output, and search bounds

Question 4

GATE 2015.

While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is

• A. 65

• B. 67

• C. 69

• D. 83

Answer: B. 67. Place 71 at the root, 65 left, 84 right, 69 at 65.right, 67 at 69.left, and 83 at 84.left. From level 0, 67 reaches level 3; 83 reaches level 2. The trap is choosing the last inserted or smallest key. Practice this question.

Question 5

GATE 2015.

Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?

I.   3, 5, 7, 8, 15, 19, 25

II.  5, 8, 9, 12, 10, 15, 25

III. 2, 7, 10, 8, 14, 16, 20

IV. 4, 6, 7, 9, 18, 20, 25

• A. I and IV only

• B. II and III only

• C. II and IV only

• D. II only

Answer: A. I and IV only. Distinct-key BST inorder output increases. Sequences I and IV increase throughout. Sequence II falls at 12 -> 10; sequence III falls at 10 -> 8. The trap is reconstructing trees instead of scanning for a decrease. Practice this question.

Question 6

ISRO 2017.

A binary search tree is used to locate the number 43. Which one of the following probe sequences is not possible during the search?

• A. 61, 52, 14, 17, 40, 43

• B. 10, 65, 31, 48, 37, 43

• C. 81, 61, 52, 14, 41, 43

• D. 17, 77, 27, 66, 18, 43

Answer: D. For target 43, 17, 77, 27 gives interval (27, 77). Probe 66 tightens it to (27, 66), so 18 cannot follow. All other paths retain 43 within their bounds. The trap is checking only the latest move and forgetting earlier ancestors. Practice this question.

Balanced versus worst-case complexity

Question 7

Coal India 2020.

For a balanced binary search tree with n elements, the time required to search a given element is:

• A. O(log n)

• B. O(n log n)

• C. O(n² log n)

• D. O(n²)

Answer: A. O(log n). A balanced 15-node BST can have edge-height 3, so a root-to-leaf search uses at most four comparisons. Each one discards one entire side. The trap is confusing one search with whole-tree processing. Search follows height, which balance keeps logarithmic. Practice this question.

Question 8

GATE 2015.

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

• A. Θ(log n) for both insertion and deletion

• B. Θ(n) for both insertion and deletion

• C. Θ(n) for insertion and Θ(log n) for deletion

• D. Θ(log n) for insertion and Θ(n) for deletion

Answer: B. Θ(n) for both insertion and deletion. Keys 10, 20, 30, 40, 50 form an edge-height 4 chain. Inserting 60 or deleting 50 may walk it. The trap is assuming every BST is balanced. Implement these cases in the Coding for Placements course. Practice this question.

Deleting nodes with one child or two children

Remove a leaf directly. Splice a one-child node's child into its place. For two children, copy the inorder successor or predecessor, then delete it from its old position.

Question 9

Bihar STET 2025.

In a Binary Search Tree (BST), the operation of deleting a node with one child involves:

• A. Removing the node and replacing it with its only child (left or right)

• B. Removing the node and replacing it only with its left child

• C. Removing the node and replacing it with its parent

• D. Removing the node without reconnecting its child

Answer: A. In Panel A, deleting 30 changes 50.left from 30 to 40; it does not discard 40. The splice also works for a left child. The trap is assuming the child must be left-sided, or setting the parent's pointer to null and losing the subtree. Practice this question.

Question 10

Capgemini 2024.

In the delete operation of a BST, we need the inorder successor (or predecessor) of a node when the node being deleted has both its left and right children non-empty. Which of the following is true about the inorder successor needed in the delete operation?

• A. Inorder successor is always a leaf node

• B. Inorder successor is always either a leaf node or a node with an empty left child

• C. Inorder successor may be an ancestor of the node

• D. Inorder successor is always either a leaf node or a node with an empty right child

Answer: B. The successor is the right subtree's minimum, so it cannot have a left child. In Panel B, 60 has right child 65, proving it need not be a leaf. The named trap is swapping “empty left child” for “empty right child.” Practice this question.

Height extremes and counting BSTs

Question 11

GATE 2017.

Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are:

Note: The height of a tree with a single node is 0.

• A. 4 and 15 respectively.

• B. 3 and 14 respectively.

• C. 4 and 14 respectively.

• D. 3 and 15 respectively.

Answer: B. 3 and 14 respectively. A perfect edge-height 3 tree holds 1 + 2 + 4 + 8 = 15 nodes. A 15-node chain has 14 edges. The trap is mixing levels with edges: four levels mean height 3 under the stated convention. Practice this question.

Question 12

GATE 2008.

How many distinct BSTs can be constructed with 3 distinct keys?

• A. 4

• B. 5

• C. 6

• D. 9

Answer: B. 5. For keys 1, 2, 3, root 1 allows two right-subtree shapes; root 2 allows one; root 3 allows two left-subtree shapes. Thus 2 + 1 + 2 = 5. The trap is using 3! = 6, which counts insertion orders, not shapes. Practice this question.

Check the answer pattern, repair the weak operation and continue

Answer key: 1-B, 2-B, 3-B, 4-B, 5-A, 6-D, 7-A, 8-B, 9-A, 10-B, 11-B, 12-B.

Rebuild each missed tree, then retry after one day. Questions 1 and 3 also appear in the binary tree MCQ set, where they support a broad comparison of tree families; here they anchor a focused progression through BST search, deletion, complexity and shape counting. Use the DSA using Java course for implementation.

Short version: maintain the subtree range, trace each comparison, express cost through height, and classify deletion by zero, one or two children.