Worst-case search time in an unbalanced BST built from sorted input?
Options
- O(1)
- O(log n)
- O(n) (Correct option)
- O(n log n)
Answer
O(n)
Why
Inserting 1, 2, 3, 4, 5 in order into a plain BST makes each new key the right child of the previous one. The 'tree' is really a straight line, like a linked list.
Searching then visits every node: O(n).
Self-balancing trees (AVL, red-black) reorganize themselves to keep height about log n, guaranteeing O(log n).
Remember
Unbalanced BST can degrade to O(n).