Exercises — BST — worst case O(n) — motivation for balancing

WHAT: each of these operations walks one path from the root down. WHY: at every node you compare and go either left or right — never both — so you visit at most $h+1$ nodes ($h$ edges). Answer: $O(h)$.

$\lfloor {\log }_{2}n\rfloor \le h\le n-1$ Lower wall = perfectly packed (bushy); upper wall = a stick.

A linked list — see Linked List — O(n) search. Search cost $=O(n)$, because you must potentially walk every node one after another.

WHAT: each key is larger than everything already inserted, so every comparison sends it right.

10
  \
   20
     \
      30
        \
         40

WHY it looks like this: $20>10$ → right; $30>20$ → right; $40>30$ → right. Never branches → a stick. $n=4$, so $h=n-1=3$.

Step by step:

• $30$ → root.
• $10<30$ → left of $30$.
• $40>30$ → right of $30$.
• $20$: $20<30$ → left to $10$; $20>10$ → right of $10$.
• $50$: $50>30$ → right to $40$; $50>40$ → right of $40$.

      30
     /   \
   10     40
     \      \
      20     50

Longest root-to-leaf path: $30\to 10\to 20$ (or $30\to 40\to 50$), $2$ edges → $h=2$.

Any fully sorted order (increasing $10,20,30,40,50$ or decreasing $50,40,30,20,10$) makes a stick. Maximum height $=n-1=4$.

WHY this sum: level $i$ holds at most $2^i$ nodes; a perfect tree hits that max on every level. Levels $0\dots 4$: $n=2^0+2^1+2^2+2^3+2^4=2^5-1=31$ (Geometric series with ratio 2 — see Geometric series.) Check: ${\log }_{2}31\approx 4.95$, so $\lfloor {\log }_{2}31\rfloor =4=h$. ✓

• Worst (stick): $h=n-1=999,999$ edges → up to $1,000,000$ visits.
• Best (bushy): $h=\lfloor {\log }_{2}10^6\rfloor =19$ → about $20$ visits. The gap: roughly $\frac{10^6}{20}=50,000\times$ faster when balanced. This factor of ~$n/\log n$ is exactly what balancing buys you.

WHAT: sum the per-level maxima. $n\le {\sum }_{i=0}^h{2}^i=2^{h+1}-1.$ WHY the bound flips into a height bound: solve for $h$: $n\le 2^{h+1}-1\Rightarrow n+1\le 2^{h+1}\Rightarrow {\log }_2(n+1)\le h+1\Rightarrow h\ge {\log }_2(n+1)-1.$ So no matter how bushy you pack, you cannot get below $\approx {\log }_{2}n$. That is the unbeatable floor — the lower wall.

(a) Plain BST: every key goes right → stick → $h=n-1=O(n)$. (b) AVL tree: after each insert it checks a balance factor and performs rotations to keep left/right heights within 1, giving $h=O(\log n)$. See AVL Trees — rotations and balance factor. One-sentence difference: the AVL restructures on the fly so sorted input can never grow a stick, whereas the plain BST silently accepts the stick.

The half-truth: random insertion order gives expected height $O(\log n)$ — often fine in practice. Why it fails as a guarantee:

1. You often can't shuffle — data arrives streaming (logs, time series, auto-increment IDs) and must be searchable immediately.
2. An adversary (or just unlucky already-sorted data) can still hand you the worst case; expectation ≠ guarantee. Big-O worst case (see Big-O notation) stays $O(n)$. Self-balancing structures give a hard $O(\log n)$ ceiling for every input, which shuffling cannot.

• BST wins: insert/delete in $O(\log n)$ — a sorted array needs $O(n)$ to shift elements.
• Array wins: raw random-access/cache locality and zero pointer overhead — contiguous memory, $O(1)$ index access. Both share the idea of halving the search space; they differ in how flexibly you can mutate.

Existence of the tall tree: insert $1,2,\dots ,n$ ascending → stick → $h=n-1$. (Constructive, always works.) Existence of the short tree: insert keys by repeatedly choosing the median of the remaining range as the next key (median-first / recursive-midpoint order). The first key is the overall median → root splits keys into two equal halves; recurse on each half. Each level fills before the next, so height $=\lfloor {\log }_{2}n\rfloor$. What this proves: the same key set spans the entire height range $[\lfloor {\log }_{2}n\rfloor ,n-1]$ purely by order. Therefore a plain BST's performance is a property of input order, not the keys — so it can offer no worst-case guarantee, which is the whole motivation for self-balancing.

WHAT: in a stick $1\to 2\to \cdots \to n$, searching for key $k$ visits $k$ nodes (you walk from $1$ down to $k$). Sum: $T(n)={\sum }_{k=1}^{n}k=\frac{n(n+1)}{2}.$ Big-O: $\frac{n(n+1)}{2}=O(n^2)$. Contrast: in a balanced tree each search is $\le \lfloor {\log }_{2}n\rfloor +1$, so the total is $O(n\log n)$ — a full order-of-magnitude cheaper for building an index of all keys.

Minimum possible: $\lfloor {\log }_{2}10^6\rfloor =19$. AVL ceiling: $1.44{\log }_2(10^6+2)-0.328\approx 1.44(19.93)-0.328\approx 28.36$, so $h\le 28$. Gap meaning: AVL never lets the tree exceed ~$1.44\times$ the perfect height. So even in its worst case an AVL is at most ~$28$ visits vs the perfect $\sim 20$ — still tiny, and lightyears better than the $10^6$ of a stick. The constant $c\approx 1.44$ is the small price for a hard guarantee. See Red-Black Trees for a looser ($c=2$) but cheaper-to-maintain alternative.

• Missed L1/L2 → reread Tree height and depth and the parent's height-bound section.
• Missed L3 → drill the Geometric series sum $2^{h+1}-1$ until it's reflex.
• Missed L4/L5 → the concept (order controls shape controls cost controls the need for balancing) hasn't clicked yet — reread the parent's "WHY this motivates balancing".