Height and Leaf Bounds of a Binary Search Tree

Intuition

A BST enforces only the ordering invariant (left < node < right), not balance. So its shape depends entirely on insertion order, and any universally true claim must hold for every possible shape — from a perfectly balanced tree to a degenerate chain.

Result

For a BST on $n$ nodes (height/depth counted in edges, root at depth $0$):

• Height: minimum $\lceil \log_2 n\rceil$ (balanced), maximum $n-1$ (degenerate chain). So depth is at most $n-1$ always.
• Leaves: minimum $1$ (a chain has a single leaf), maximum $\lceil n/2\rceil$ (complete tree). So you can never claim "at least $\log n$ leaves" or "$n-1$ leaves."

Worked example ($n=4$)

Degenerate (insert 1,2,3,4):     Balanced:
1                                    2
 \                                 /   \
  2          depth = 3 = n-1      1     3
   \         1 leaf                      \
    3                                     4
     \       depth = 2 = ceil(log2 4)
      4      2 leaves (max = ceil(4/2)=2)

The chain reaches depth $n-1=3$; no shape exceeds it. Max leaves is $\lceil 4/2\rceil=2$, so $n-1=3$ leaves is impossible.

Pitfall: Treating a BST as automatically balanced. The tempting $\log n$ answers assume balance, which a plain BST does not guarantee — the degenerate chain (depth $n-1$, one leaf) breaks them. Only a self-balancing tree (AVL, red-black) forces $\Theta(\log n)$ height.