What is a binary search tree and what is its key property?

• A. A BST is a balanced tree where every node has the same number of children.
• B. A BST stores keys in random order for fast insertion.
• C. A BST stores keys in sorted order where left subtree keys are less than the node and right subtree keys are greater, enabling efficient search, insert, and delete.
• D. A BST is a graph with cycles.

Answer: (C)

The main idea being tested is how a binary search tree uses a specific ordering of keys to enable fast lookups and updates. In a binary search tree, each node stores a key, and all keys in the left subtree are strictly smaller than the node’s key, while all keys in the right subtree are strictly greater. This invariant lets you locate any target by comparing it to the current node: if the target is equal, you’re done; if it’s smaller, you move to the left subtree; if larger, you move to the right subtree. Because each comparison narrows the search space, operations like search, insert, and delete run efficiently on average—logarithmic time in a balanced tree. If the tree becomes unbalanced, performance can drop toward linear time, which is why balancing schemes exist. Also, an in-order traversal of a BST yields keys in sorted order, reflecting how the structure organizes data.