Worst-case height of an unbalanced BST

Intuition

Most BST operations (search, insert, find-min/max) walk a single root-to-node path, so their cost is bounded by the tree height $h$. A balanced tree keeps $h=\Theta(\log n)$, but a plain BST gives no balance guarantee — its shape depends entirely on insertion order.

Result

If keys arrive in sorted (increasing or decreasing) order, every new node attaches at the end of one spine, degenerating the tree into a single chain ("linked list") of $n$ nodes. Then $h = n-1 = \Theta(n)$ so search, find-min, and find-max all cost $O(n)$ in the worst case — not $O(\log n)$.

Worked example

Finding the minimum = walk down left children until none remain:

Insert n, n-1, ..., 2, 1  ->  left chain:

   n
  /
 n-1
 /
...
 /
 1   <- minimum, n-1 steps down => O(n)

The leftmost path has length $n-1$, so reaching key $1$ takes $\Theta(n)$ steps.

Exam trick: When a question says worst case for a plain BST, the answer is $O(n)$. Reflexively answering $O(\log n)$ gives the balanced/average-case bound; that only holds with a balancing scheme such as AVL or red-black.