Which statement accurately contrasts an unbalanced binary search tree with a balanced BST in terms of height and worst-case search time?

• A. Unbalanced: height O(log n); Balanced: height O(n)
• B. Unbalanced: height O(n); Balanced: height O(log n)
• C. Both have height O(log n)
• D. Unbalanced: height O(n log n); Balanced: height O(log n)

Answer: (B)

The main idea is that search time in a binary search tree grows with its height, because you follow a single path from the root down to the target. An unbalanced BST can degrade into a chain if nodes are added in a sorted order, giving a height of n. In that worst case you might compare against every node, so the worst-case search time is O(n). A balanced BST keeps its height around log n by spreading nodes across levels evenly, so the longest path from root to a leaf is about log2(n), and the worst-case search time is O(log n). So the statement that unbalanced has height O(n) with worst-case O(n), while balanced has height O(log n) with worst-case O(log n), is the correct description. The other options misstate the potential heights for the unbalanced or balanced cases.