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

Before you can understand why a BST can secretly become slow, you need a small toolbox of ideas. The parent note tosses around words like "node", "height", "$O(n)$", "${\log }_{2}n$", and "geometric series" as if you already own them. Here we forge each one, in an order where every new idea only uses ideas already built.

1. What is a tree? (node, edge, root, leaf)

Forget code for a second. A tree is just dots connected by lines, drawn top-down, where each dot has exactly one line coming from above it — except the very top dot, which has none.

Why the topic needs this: every cost in a BST is counted by walking along edges from the root downward. If you can't see nodes and edges clearly, you can't count that walk. Look at the picture: the root is the yellow dot at top, leaves are the green dots at the bottom, and every blue line is one edge.

Link to the fuller definitions: Binary Search Tree — definition and property and Tree height and depth.

2. What is a Binary Search Tree? (the data structure itself)

We have a binary tree (each node has $\le 2$ children). A Binary Search Tree is that same shape plus one ordering rule that turns it into a fast lookup machine.

Why the topic needs this: everything in the parent note — the cost $O(h)$, the sorted-insert disaster, the motivation for balancing — is a property of this structure. If the BST is not defined, none of it has meaning.

3. Less-than, greater-than, and equal keys: $<$, $>$, $=$

The BST rule uses two tiny symbols. Let's not assume them.

Why the topic needs this: the BST property ("left < node < right") is what makes searching directional — at each node you can decide "go left" or "go right" and throw away the other side. That throwing-away is where speed comes from. Equal keys would break the decision, which is why we fix a rule for them.

4. Levels, height $h$, and depth (the star of the show)

First, one word the doubling arguments secretly depend on.

Now the two most important quantities.

Why the topic needs this: the parent note's headline claim is "cost = $O(h)$". Every search/insert/delete walks one path from the root down, and $h$ is the length of the longest such path — the worst walk you could be forced to take. So $h$ is the cost. Everything else on the page is about how big or small $h$ can be.

The symbol $h$ is just a nickname ("$h$ for height") so we don't have to write "the height of the tree" every single time.

5. The letter $n$: how many nodes

Why the topic needs this: we want to know how bad things get as the tree grows. Asking "how big can $h$ get for a tree of $n$ nodes?" only makes sense once $n$ names the size. The two bounds in the parent note, $\lfloor {\log }_{2}n\rfloor \le h\le n-1$, both compare $h$ against this count $n$.

6. Worst-case height: deriving $h\le n-1$ from scratch

Before quoting the parent note's bound, let's build it.

Every non-empty level must contain at least one node (if a level were empty, nothing could hang below it, so the tree would already have ended). To reach height $h$, the tree needs levels $0,1,2,\dots ,h$ — that is $h+1$ distinct levels, each holding at least one node. So:

$n\ge \underset{h+1\text{ levels}}{\underbrace{1+1+\cdots +1}}=h+1.$

Rearranging, $h\le n-1$. And this is achieved exactly when every level holds precisely one node — the "stick" tree, where each node has a single child.

Why the topic needs this: this $n-1$ is the $O(n)$ villain of the whole topic. We just showed why no tree can be taller and which shape hits the limit.

7. Doubling per level, and powers $2^i$

Now the opposite question — how short can we make it? — needs one tool: the fact that levels can grow fast.

Why the topic needs this: the fact "level $i$ holds at most $2^i$ nodes" is the seed of the best-case height. Doubling grows so fast that even a short tree holds an enormous crowd.

8. Adding up the doublings: the geometric series

To find the total capacity of a tree that is full up to height $h$, we add up every level's maximum.

Why the topic needs this: this formula tells us the maximum number of nodes a tree of height $h$ can hold. Turning that around ("if I have $n$ nodes, how few levels can I get away with?") produces the best-case height next.

9. Undoing the exponent: ${\log }_{2}n$ (and the best-case height)

The exponent asks: "$2$ to the power of what gives me $n$?" The answer to that question is the logarithm.

Now the best-case height. To hold all $n$ nodes in the fewest levels, pack every level full. From the capacity formula, a tree of height $h$ holds at most $2^{h+1}-1$ nodes, so we need:

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

Since $h$ must be a whole number, we round the requirement up: the smallest legal height is $h=\lceil {\log }_2(n+1)\rceil -1$, which equals the parent note's $\lfloor {\log }_{2}n\rfloor$ for every $n\ge 1$ (both give: $n=1\to 0$, $n=3\to 1$, $n=7\to 2$, $n=8\to 3$). Either form names the same integer — the shortest a BST on $n$ keys can be.

Why the topic needs this: $\log$ is the opposite tool to the exponent $2^i$. Since capacity grows like $2^h$, the height needed for $n$ nodes shrinks like ${\log }_{2}n$. That ${\log }_{2}n$ floor is the fast, "bushy" end of the height range — the target every balancing scheme aims for.

10. Big-O: the shape-of-growth language

Finally, $O(n)$, $O(\log n)$, $O(h)$. These are not exact counts — they describe how the cost grows as the tree gets bigger, ignoring constants.

Why the topic needs this: Big-O is the ruler we measure heights with. Saying "cost is $O(h)$, and $h$ is between $O(\log n)$ and $O(n)$" is the parent note's whole thesis compressed into one sentence.

How these foundations feed the topic

How to read this diagram: arrows mean "is needed to build". Start at the top boxes (raw ideas) and follow the arrows downward; each box only uses ideas from the boxes pointing into it. The bottom box, "Motivation for balancing", is the parent topic — everything flows into it.

Equipment checklist

Answer each before reading the parent note. If any stumps you, re-read its section above.