Visual walkthrough — BST — worst case O(n) — motivation for balancing

Every symbol below is drawn before it is used. If a word looks scary, wait one line — the picture is coming.

---

Step 1 — What is a tree, and what is a "path"?

WHAT. A tree is a set of circles called nodes, each holding a number (a key), joined by lines called edges. One special node at the very top is the root. From the root, edges go down to children. A node with no children is a leaf.

WHY. Before we can talk about how tall a tree is, we must agree on what "top", "down", and "a path down" mean. A BST operation (search / insert / delete) never wanders sideways — it starts at the root and walks straight down, one edge at a time, until it stops. So the only thing that can make it slow is a long downward path.

PICTURE. The red arrows trace one root-to-leaf path. Count the edges it crosses — that count is what we will call the path's length.

Here, in $h$, the letter $h$ just means "how many downward steps in the worst possible walk."

---

Step 2 — Why does cost equal height?

WHAT. To search for a key, you stand at the root, compare, and move to exactly one child (left if you want something smaller, right if bigger — that is the BST property). You repeat until you find it or fall off the bottom.

WHY. Because you take one step per level, the number of comparisons is at most the number of levels you can descend — which is the height $h$ plus one. Using Big-O notation (which throws away the "+1" and constant factors), the cost is:

$\text{cost of one operation}=\underset{\text{"grows no faster than"}}{\underbrace{O}}\left(\underset{\text{longest descent}}{\underbrace{h}}\right)$

The symbol $O(\cdot )$ answers the question "how does the work grow as the tree grows?" — it ignores small stuff and keeps only the shape of the growth. We use it (not exact counts) because we care about scaling, not whether it's $h$ or $h+3$.

PICTURE. Follow the blue walk: at every circled node you make one decision and drop one level. The number of blue steps can never beat $h$.

Recall Why not count sideways moves?

A BST search never moves sideways — it goes strictly down. So the only thing that limits its speed is how deep the tree can go. ::: Because each comparison sends you to exactly one child (down one level), the total work is bounded by the number of levels, i.e. the height.

So the entire question "is a BST fast?" collapses to "how big can $h$ get?" Steps 3–7 answer that from both ends.

---

Step 3 — The same keys, two shapes (the whole mystery in one figure)

WHAT. Take the five keys $1,2,3,4,5$. Insert them in sorted order, then insert them in a mixed order. Watch two completely different trees appear.

WHY. Insertion order decides where each new key lands. When a key is larger than the current node, it turns right; when smaller, left. Sorted keys are always larger than everything before them, so they always turn right — the tree never branches. Mixed keys turn both ways, so the tree spreads out.

PICTURE. Left = the "stick" (sorted inserts). Right = the "bush" (mixed inserts). Same numbers, wildly different heights. Count the edges on the longest path in each.

---

Step 4 — The worst case: derive $h_{\max }=n-1$

WHAT. We now find the tallest tree possible for $n$ nodes. Call it $h_{\max }(n)$ — "the biggest height any legal tree on $n$ nodes can have."

WHY. To make a tree as tall as possible, give every node exactly one child. Then each new node adds a whole new level instead of filling an existing one. This is exactly what sorted insertion produces (see a linked list — same shape!).

PICTURE. Watch the stick grow: node at level $0$, level $1$, ..., level $n-1$. Each of the $n$ nodes sits alone on its own level.

Now count the levels. With one node per level and $n$ nodes, the levels are numbered $0,1,2,\dots ,n-1$. The longest path runs from level $0$ to level $n-1$, crossing:

$h_{\max }(n)=\underset{\begin{array}{c}\text{edges between}\\ \text{level 0 and level }n-1\end{array}}{\underbrace{(n-1)}}=n-1$

Here $n$ is the node count and $n-1$ counts the gaps between the $n$ stacked nodes.

---

Step 5 — The best case: why each level holds at most $2^i$ nodes

WHAT. To make a tree as short as possible, we must cram the most nodes into the fewest levels. First we ask: how many nodes can level $i$ hold?

WHY. Each node has at most 2 children (that's what "binary" means). So going down one level, the node count can at most double. Level $0$ holds $1$ node (the root); level $1$ holds at most $2$; level $2$ at most $4$; and in general:

$\text{max nodes on level }i=\underset{\begin{array}{c}\text{doubling once}\\ \text{per level}\end{array}}{\underbrace{2^i}}$

The exponent $i$ is the level number, and $2$ is "each parent makes up to two children."

PICTURE. Level $0$: $2^0=1$. Level $1$: $2^1=2$. Level $2$: $2^2=4$. Level $3$: $2^3=8$. Watch the width double each row.

---

Step 6 — Add up the full levels (a geometric series)

WHAT. Suppose the tree has height $h$ and every level is packed full. Total nodes $n$ is the sum of all levels' capacities:

$n\le \underset{\text{level }0}{\underbrace{2^0}}+\underset{\text{level }1}{\underbrace{2^1}}+\cdots +\underset{\text{level }h}{\underbrace{2^h}}$

WHY. This is a geometric series — a sum where each term is the previous one times a fixed ratio (here the ratio is $2$). We use the closed form of this series so we don't have to add term by term:

${\sum }_{i=0}^h{2}^i=2^{h+1}-1$

Read it as: "one more than the last term, doubled, minus one." The $2^{h+1}$ is double the biggest level, and the $-1$ trims the overshoot.

PICTURE. The staircase blocks (widths $1,2,4,8$) stack up to just one short of the next power of two — the pale-yellow bar of height $2^{h+1}-1$.

Now solve for $h$ — we invert the relationship because we want height in terms of the node count $n$:

$n\le 2^{h+1}-1⟹n+1\le 2^{h+1}⟹{\log }_2(n+1)\le h+1⟹h\ge {\log }_2(n+1)-1$

We apply ${\log }_2$ (the "how many times must I double $1$ to reach this?" function) precisely because it undoes the doubling that built the levels. The smallest legal height is therefore about $\lfloor {\log }_{2}n\rfloor$.

---

Step 7 — Edge & degenerate cases (never leave a gap)

WHAT / WHY / PICTURE — the corners the formulas must still survive:

The figure shows the tiny cases side by side: notice how for $n=1,2$ the "fast" and "slow" bounds are the same tree. The gap between $\log n$ and $n-1$ only yawns open once $n$ is large — which is exactly when it matters.

---

The one-picture summary

WHAT. One graph. Horizontal axis = number of nodes $n$. Vertical axis = height $h$. Two curves: the ceiling $h=n-1$ (the stick) and the floor $h=\lfloor {\log }_{2}n\rfloor$ (the bush). Every legal BST lives in the shaded band between them.

WHY. This single frame is the parent note: cost $=O(h)$, and $h$ is trapped between $\log n$ and $n$. A plain BST can sit anywhere in the band — including on the deadly straight line up top. AVL and Red-Black trees are the machinery that pins you to the bottom curve forever.

Recall Feynman: tell the whole walkthrough to a 12-year-old

A tree is dots joined by lines, with a boss dot on top. When you look for a number, you start at the boss and take one step down each time — smaller goes left, bigger goes right — so the number of steps is just how deep the tree goes. Now here's the trick: if you feed the tree numbers already in order (1, 2, 3, 4, 5), each new one is always bigger, so it always goes right, and the tree grows into a long ladder — you'd have to climb every rung. That's the slow case, and its depth is $n-1$ (one less than the number of dots). But if you feed the numbers mixed up, the tree fills out sideways: row 1 has 1 dot, row 2 has 2, row 3 has 4 — doubling each time. Doubling means the depth to hold $n$ dots is only about ${\log }_{2}n$ (how many times you double 1 to reach $n$). So every tree's depth is squished between "about $\log n$" (fast, bushy) and "$n-1$" (slow, stick). Balancing trees are just robots that keep shoving your tree down to the fast, bushy bottom no matter what order you hand them.

Connections

• BST — worst case O(n) — motivation for balancing (index 3.4.6)
• Binary Search Tree — definition and property
• Tree height and depth
• Binary Search — divide and conquer
• AVL Trees — rotations and balance factor
• Red-Black Trees
• Linked List — O(n) search
• Big-O notation
• Geometric series