BST — worst case O(n) — motivation for balancing: Worked examples

Before we start, one reminder of the two symbols we use everywhere:

The cost of search/insert/delete is $O (h)$ because each of them walks one path from the root downward — never sideways, never back up. So "how slow is my tree?" is literally "how tall is my tree?"

The scenario matrix

Every BST-height situation you can be handed falls into one of these cells. Our job below is to hit all of them.

Cell	Case class	What makes it special	Example
A	Degenerate right stick — sorted increasing insert	every key goes right; $h = n - 1$	Ex 1
B	Degenerate left stick — sorted decreasing insert	every key goes left; $h = n - 1$	Ex 2
C	Zig-zag stick — alternating extreme inserts	still one node per level; $h = n - 1$	Ex 3
D	Perfectly full tree — the best case	every level packed; $h = ⌊ lo g_{2} n ⌋$	Ex 4
E	Degenerate input, empty & single node	$n = 0$ and $n = 1$ edge cases	Ex 5
F	Mixed / "bushy-ish" — realistic order	$h$ somewhere in the middle	Ex 6
G	Real-world word problem — sorted timestamps	why "it works on my laptop" fails at scale	Ex 7
H	Exam twist — count nodes from a height, or invert the bound	reading the formula backwards	Ex 8
I	Limiting behaviour — how big is the gap $O (n)$ vs $O (lo g n)$ ?	the whole reason balancing matters	Ex 9

The two "sign/quadrant"-style extremes for a tree are lean-right (Cell A) and lean-left (Cell B); the "zero/degenerate" inputs are Cell E; the "limiting value" is Cell I. That's the whole grid — let's walk it.

Cell A — Degenerate right stick

Worked example Insert the keys

$10, 20, 30, 40, 50$ (increasing). What is $h$ , and what is the cost of searching for $50$ ? Forecast: Guess before reading — will this tree be bushy or a stick? How many edges to reach $50$ ?

Step 1. Insert $10$ → it becomes the root. Why this step? The first key always becomes the root; there's nothing to compare against.

Step 2. Insert $20$ . Compare $20$ vs $10$ : $20 > 10$ , so by the BST property it goes to the right. Why this step? The BST rule says "bigger keys live in the right subtree," and $20 > 10$ , so right it goes.

Step 3. Insert $30, 40, 50$ . Each new key is bigger than everything already in the tree, so it keeps travelling right, right, right — never once turning left. Why this step? A sorted-increasing stream means every comparison gives the same answer ("go right"), so the tree never branches. See the figure.

Step 4. Count edges from root $10$ down to $50$ : $10 \to 20 \to 30 \to 40 \to 50$ = $4$ edges. So $h = 4$ . Why this step? Height = edges on the longest path, and here the whole tree is one path.

With $n = 5$ : $h = n - 1 = 5 - 1 = 4$ . ✓

Verify: Searching for $50$ visits every node ( $10, 20, 30, 40, 50$ ) = $5$ comparisons, i.e. $O (n)$ . This is identical to scanning a linked list. The "halving magic" of binary search never happened because we never discarded a subtree.

Cell B — Degenerate left stick

Worked example Insert the keys

$50, 40, 30, 20, 10$ (decreasing). What is $h$ ? Forecast: Same $n = 5$ as Cell A. Same height, or different?

Step 1. Insert $50$ → root. Why this step? First key is always the root.

Step 2. Insert $40$ : $40 < 50$ , so it goes left. Why this step? BST property: smaller keys live in the left subtree, and $40 < 50$ .

Step 3. Insert $30, 20, 10$ . Each is smaller than everything present, so each keeps going left. Why this step? A sorted-decreasing stream means every comparison answers "go left," so the tree leans the other way but is still a stick.

Step 4. Edges from $50$ down to $10$ = $4$ . So $h = 4 = n - 1$ .

Verify: Mirror image of Cell A — direction ("left" vs "right") does not matter for height. Both sorted orders give the same worst case $h = n - 1$ . This is why the parent note says "increasing or decreasing."

Cell C — Zig-zag stick

Worked example Insert

$30, 10, 20, 25, 22$ . Is this a stick even though inserts alternate direction? Forecast: The keys aren't monotone. Surely this branches into a bush... or does it?

Step 1. Insert $30$ → root. Insert $10$ : $10 < 30$ → left child of $30$ . Why this step? Standard BST placement.

Step 2. Insert $20$ : $20 < 30$ (go left to $10$ ), then $20 > 10$ (go right). So $20$ is the right child of $10$ . Why this step? We follow the comparison at each node; two comparisons place $20$ .

Step 3. Insert $25$ : $25 < 30$ →left to $10$ ; $25 > 10$ →right to $20$ ; $25 > 20$ →right. So $25$ is right child of $20$ . Insert $22$ : $22 < 30$ → $10$ ; $22 > 10$ → $20$ ; $22 > 20$ → $25$ ; $22 < 25$ →left. So $22$ is left child of $25$ . Why this step? Each key still adds exactly one node at a new deepest level — no node ever gets two children.

Step 4. The path is $30 \to 10 \to 20 \to 25 \to 22$ = $4$ edges, so $h = 4 = n - 1$ .

Verify: With $n = 5$ we again get $h = 4$ . Lesson: "stick" is about shape, not about sorted keys. A crafted zig-zag order is just as degenerate. An adversary who knows your tree can build $O (n)$ shapes even with wild-looking keys — reinforcing why we need self-balancing.

Cell D — Perfectly full tree (best case)

Worked example Insert

$40, 20, 60, 10, 30, 50, 70$ . Find $h$ and confirm it equals $⌊ lo g_{2} n ⌋$ . Forecast: $n = 7$ . Guess the height — is it near $6$ (stick) or near $2$ ?

Step 1. Insert $40$ → root. Insert $20$ (left of $40$ ) and $60$ (right of $40$ ). Why this step? We deliberately insert the median first, then the medians of each half, so both sides fill.

Step 2. Insert $10, 30$ under $20$ and $50, 70$ under $60$ . Why this step? Each of the four leaves is the median of its remaining range, so every level fills completely — this is the "pack each level full" idea from the parent note.

Step 3. Count levels: level $0$ = { $40$ }, level $1$ = { $20, 60$ }, level $2$ = { $10, 30, 50, 70$ }. Longest path has $2$ edges, so $h = 2$ . Why this step? Level $i$ holds up to $2^{i}$ nodes; here $2^{0} + 2^{1} + 2^{2} = 1 + 2 + 4 = 7 = n$ , a full tree.

Step 4. Check the formula: $⌊ lo g_{2} 7 ⌋ = ⌊ 2.807 \dots ⌋ = 2$ . ✓

Verify: Same $7$ keys inserted sorted would give $h = 6$ . Here $h = 2$ . Searching costs $\leq 3$ comparisons instead of $7$ — the halving magic is back.

Cell E — Empty and single-node (degenerate inputs)

Worked example What is

$h$ for $n = 0$ (empty tree) and $n = 1$ (one node)? Forecast: Does the formula $⌊ lo g_{2} n ⌋$ even survive here?

Step 1. $n = 1$ : one node, no edges. By the edge convention, $h = 0$ . Why this step? Height counts edges; a lonely node has none. (This is exactly the off-by-one mistake the parent warns about.)

Step 2. Check the bound at $n = 1$ : $⌊ lo g_{2} 1 ⌋ = 0$ and $n - 1 = 0$ . Both bounds collapse to $0$ , and indeed $h = 0$ . ✓ Why this step? At $n = 1$ the "best" and "worst" tree are the same tree, so the bounds must meet.

Step 3. $n = 0$ : no nodes, no root. Height is undefined (some texts write $h = - 1$ ). Cost of searching an empty tree = $0$ comparisons. Why this step? You can't walk a path in a tree that doesn't exist — the operation returns "not found" immediately.

Verify: $lo g_{2} 0$ is $- \infty$ , which is why $n = 0$ sits outside the formula and must be handled as a special case in code. Always guard if (root == null) first.

Cell F — Mixed / bushy-ish (realistic middle)

Worked example Insert

$50, 30, 70, 20, 60$ . Find $h$ and show it lands strictly between the two bounds. Forecast: $n = 5$ . Worst is $4$ , best is $⌊ lo g_{2} 5 ⌋ = 2$ . Guess where this one lands.

Step 1. Insert $50$ →root; $30$ →left; $70$ →right. Why this step? $30 < 50$ left, $70 > 50$ right — the tree already branches both ways.

Step 2. Insert $20$ : $20 < 50$ → $30$ ; $20 < 30$ →left. So $20$ is left child of $30$ . Insert $60$ : $60 > 50$ → $70$ ; $60 < 70$ →left. So $60$ is left child of $70$ . Why this step? Real, unsorted data tends to branch — but not perfectly.

Step 3. Longest path: $50 \to 30 \to 20$ (or $50 \to 70 \to 60$ ), both $2$ edges. So $h = 2$ .

Step 4. Compare with bounds: $⌊ lo g_{2} 5 ⌋ = 2 \leq h = 2 \leq n - 1 = 4$ . ✓ Why this step? We are confirming the parent's inequality $⌊ lo g_{2} n ⌋ \leq h \leq n - 1$ holds here — this tree happens to touch the best-case floor.

Verify: $h = 2$ satisfies $2 \leq 2 \leq 4$ . Not every "mixed" order gives the minimum, but this one did — showing you can be lucky without any balancing. The problem is you can't rely on luck.

Cell G — Real-world word problem (sorted timestamps)

Worked example A logging service inserts each new event keyed by its Unix timestamp into a plain BST. After one million events, searching for a specific event is timed at ~

$1, 000, 000$ comparisons instead of the expected ~ $20$ . Explain, using $h$ . Forecast: Guess: is this a bug in the search code, or a bug in the tree shape?

Step 1. Timestamps only ever increase — each new event's key is larger than every previous one. Why this step? Time moves forward, so the insertion stream is sorted-increasing → this is exactly Cell A.

Step 2. So every insert goes right, and the tree becomes a right stick of height $h = n - 1 = 999, 999$ . Why this step? Sorted input degenerates the BST; there's no bug in the search code — the shape is the bug.

Step 3. Cost $= O (h) = O (n) = O (1, 000, 000)$ , matching the measured ~million comparisons. Why this step? Cost tracks height, and height is now linear in $n$ .

Step 4. The "expected ~ $20$ " assumed a balanced tree: $⌈ lo g_{2} 1 0^{6} ⌉ \approx 20$ . Why this step? $2^{20} = 1, 048, 576 > 1 0^{6}$ , so a balanced million-node tree has height about $20$ .

Verify: The fix is a self-balancing BST, which forces $h = O (lo g n) \approx 20$ regardless of the sorted arrival order. Ratio of pain: $\frac{1 , 000 , 000}{20} = 50, 000 \times$ slower. This is the whole motivation for balancing, live.

Cell H — Exam twist (read the formula backwards)

Worked example "A BST is

perfectly full (every level completely filled) and has height $h = 4$ . Exactly how many nodes does it contain?" Forecast: We're given $h$ and asked for $n$ — the inverse of every previous example.

Step 1. A perfectly full tree of height $h$ fills levels $0$ through $h$ , with level $i$ holding exactly $2^{i}$ nodes. Why this step? "Perfectly full" is the equality case of the geometric bound $n \leq 2^{h + 1} - 1$ .

Step 2. Sum the geometric series: $n = \sum_{i = 0}^{4} 2^{i} = 2^{5} - 1 = 32 - 1 = 31$ . Why this step? $\sum_{i = 0}^{h} 2^{i} = 2^{h + 1} - 1$ ; plug $h = 4$ .

Step 3. Sanity-check the height formula the other way: $⌊ lo g_{2} 31 ⌋ = ⌊ 4.954 \dots ⌋ = 4$ . ✓ Why this step? If our $n$ is right, feeding it into the best-case height must return the given $h = 4$ .

Verify: $31$ nodes, $h = 4$ . A common wrong answer is $2^{4} = 16$ (only the last level) — but the question asks for all nodes, which is the sum $31$ .

Cell I — Limiting behaviour (the size of the gap)

Worked example For

$n = 1, 000, 000$ nodes, compute the worst-case and best-case number of comparisons, and their ratio. What does this ratio approach as $n \to \infty$ ? Forecast: Guess the ratio's order of magnitude before computing.

Step 1. Worst case: $h_{m a x} = n - 1 = 999, 999$ , so cost $\approx 1 0^{6}$ comparisons. Why this step? Sorted / degenerate input, Cell A.

Step 2. Best case: $h_{m i n} = ⌊ lo g_{2} 1 0^{6} ⌋ = 19$ , so cost $\approx 20$ comparisons. Why this step? $2^{19} = 524, 288$ and $2^{20} = 1, 048, 576$ , so $lo g_{2} 1 0^{6} \approx 19.93$ , floor $19$ .

Step 3. Ratio $= \frac{n}{lo g _{2} n} = \frac{1 , 000 , 000}{19.93} \approx 50, 171$ . Why this step? We compare $O (n)$ against $O (lo g n)$ directly; the gap is the value of balancing.

Step 4. As $n \to \infty$ , $\frac{n}{lo g _{2} n} \to \infty$ . Why this step? Any polynomial (even linear) grows without bound faster than any logarithm — see Big-O notation. So the penalty for a stick tree gets worse forever as data grows.

Verify: At a million nodes the stick is ~ $50, 000 \times$ slower; at a billion nodes it's ~ $33, 000, 000 \times$ slower. The gap explodes — which is precisely why "just use a plain BST and hope" is not acceptable at scale.

Active Recall

Which insertion orders both produce

h = n - 1

Sorted increasing (right stick) and sorted decreasing (left stick) — direction doesn't matter.

Can a non-monotone insertion order still give a degenerate stick?

Yes — a crafted zig-zag order (Cell C) can add one node per level, giving

h = n - 1

A perfectly full tree has height

h = 4

; how many nodes?

2^{5} - 1 = 31

nodes (sum the geometric series, not just the last level).

For

n = 1 0^{6}

, best-case vs worst-case comparison ratio is about?

About

50, 000 \times

(

\approx n / lo g_{2} n

), and it grows to

\infty

n \to \infty

What is

h

for a single-node tree, and why?

h = 0

, because height counts edges and a lone node has none.

Connections

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