In a binary search tree, what is the worst-case height if the tree becomes degenerate?

• A. O(n)
• B. O(log n)
• C. O(1)
• D. O(n log n)

Answer: (A)

Understanding how a binary search tree grows in the worst case: the height is the length of the longest path from the root to a leaf. If the tree becomes degenerate, each new element attaches to the end of the existing chain, making a single long path. This creates a structure that behaves like a linked list, so the longest path includes nearly all the nodes. As the number of nodes n grows, the height grows linearly with n, which is O(n). In such a degenerate tree, operations like search, insert, and delete can take linear time instead of the faster logarithmic time you’d get with a balanced BST.