In a binary search tree that degenerates into a chain, what is the worst-case time complexity for search, insert, or delete?

In a binary search tree that degenerates into a chain, what is the worst-case time complexity for search, insert, or delete?

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

Answer: (A)

The key idea is that how long a BST operation takes depends on how far you must travel from the root to reach the target. In a binary search tree, each comparison moves you down one level, so the time is proportional to the tree’s height. When the tree degenerates into a chain, every node has at most one child, turning the structure into a linear sequence of n nodes. In the worst case you may need to visit every node to find a value, insert at the end, or remove the last one, so the time grows linearly with n. That makes the worst-case time complexity for search, insert, and delete O(n). The other options would only occur under different conditions—balanced trees give O(log n); constant time isn’t possible for these operations in a typical BST; and O(n log n) isn’t the correct scaling for a single operation.