What makes a binary search tree efficient for search operations?

What makes a binary search tree efficient for search operations?

• A. Its keys are stored in random order.
• B. It uses a hash index.
• C. It stores keys in sorted order with left less than and right greater, enabling efficient search, insert, and delete.
• D. It requires every node to have two children.

Answer: (C)

The efficiency comes from how a binary search tree organizes keys: every node acts as a dividing point where all keys in the left subtree are smaller and all keys in the right subtree are larger. When you search, you compare the target with the current node’s key and then move left if the target is smaller or right if it’s larger. This choice at each step excludes roughly half of the remaining keys, so you rapidly narrow down the possible location. That fast narrowing is what makes search, insert, and delete efficient, especially when the tree remains balanced and the height grows logarithmically with the number of keys.

Storing keys in random order would not support this decisive narrowing, and using a hash index is a different approach that doesn’t preserve order or enable efficient range queries. Also, a BST does not require every node to have two children; nodes can have zero, one, or two children.