How does black-height prove a red-black tree's height stays within about 2·log n?
answer
- count only the black nodes below a node
- reds may not be neighbours on a path
- so blacks are at least half the path
- how small can a black-height b subtree be
- n at least 2^(h/2) minus one
basics
~20 sEvery path in a red-black tree carries the same black count b, and reds cannot be adjacent, so at least half of any path is black. A subtree of black-height b holds at least 2^b − 1 nodes, giving height at most 2·log2(n+1).
solid answer
~40 sDefine the black-height of a node as the number of black nodes on any downward path from it to a leaf sentinel, not counting the node itself — well defined because the invariant makes that count equal on all such paths. Two steps follow. First, a subtree whose root has black-height `b` contains at least `2^b − 1` internal nodes; you prove it by induction, since each child has black-height `b` or `b−1`. Second, because no red node has a red child and the root is black, at least half the nodes on any root-to-leaf path are black, so the root's black-height is at least `h/2` for tree height `h`. Combining, `n >= 2^(h/2) − 1`, which rearranges to `h <= 2·log2(n+1)`. That is the whole argument, and it needs no rotation case tables.
go deeper
Know the vocabulary: black-height counts black nodes on the way down, and the height is O(log n) worst case. Being able to state the bound is enough at this level.
Reproduce the two steps at a whiteboard: a black-height b subtree holds at least 2^b − 1 nodes, and blacks are at least half of any path. That is the answer expected here.
Show you know what the bound is and is not: a worst-case ceiling that no insertion order can break, not a prediction of the depth you will measure on real keys.
Frame it as the guarantee you are buying. When a latency budget depends on a worst case rather than an average, an argued bound like this is what makes the structure defensible in a design review.
## Setting up the quantity The proof rests on one derived measure. The **black-height** of a node x, written `bh(x)`, is the number of black nodes on any path from x down to a leaf sentinel, *not counting x itself*. This is only well defined because of the invariant that all such paths carry the same black count — that rule is precisely what makes black-height a property of the node rather than of a particular path. Sentinel leaves have black-height 0. The tree's black-height is `bh(root)`. Two other invariants do work here: the root is black, and no red node has a red child. ## Step 1 — a black-height b subtree is not small **Claim:** the subtree rooted at x contains at least `2^bh(x) − 1` internal nodes. *Base case.* If x is a sentinel, `bh(x) = 0` and the subtree holds `2^0 − 1 = 0` internal nodes. True. *Inductive step.* Take an internal node x with two children. Each child has black-height either `bh(x)` (if the child is red — stepping onto it adds no black to the count) or `bh(x) − 1` (if the child is black). Either way each child's black-height is at least `bh(x) − 1`. By the induction hypothesis each child's subtree holds at least `2^(bh(x)−1) − 1` internal nodes, so x's subtree holds at least `2 · (2^(bh(x)−1) − 1) + 1 = 2^bh(x) − 1` internal nodes, counting x itself. The claim holds. Notice what this says intuitively: a tree can be shallow-and-wide or it can be stretched by reds, but the *black skeleton* — the tree you would get by contracting every red node into its parent — is a tree of height `bh(root)`, and a tree of that height with the color rules in force cannot be a sparse chain. ## Step 2 — at least half of any path is black Walk any root-to-leaf path. The first node, the root, is black. No red node may be followed by another red node, so reds are never adjacent along the path — every red is either preceded or followed by a black, and no two reds share a neighbour position. Therefore reds are at most half of the path's nodes, and blacks are at least half: `bh(root) >= h/2` where `h` is the tree height. This is where the factor of two in the final bound comes from, and it is the only place it comes from. If the rules had allowed two reds in a row, blacks would only be guaranteed a third of the path, and the bound would loosen to roughly `3·log n`. ## Combining With n internal nodes: `n >= 2^bh(root) − 1 >= 2^(h/2) − 1` Add one and take base-2 logarithms of both sides: `log2(n+1) >= h/2`, so `h <= 2·log2(n+1)`. Search, insert and delete all walk one root-to-leaf path plus O(1) or O(log n) bookkeeping, so all three are O(log n) **worst case** — no input ordering can degrade them, which is the entire reason the coloring exists. ## Worked sanity check Suppose a tree's root has black-height 4. Step 1 says it holds at least `2^4 − 1 = 15` internal nodes. Conversely with a million keys, `log2(1000001) ≈ 20`, so the height is at most about 40 — and the black-height is at least 20 in the deepest legal case. In practice a tree built from random keys sits far nearer 20 than 40; the bound is a worst-case ceiling, not a prediction of typical depth. ## Where the argument goes wrong when people reproduce it - **Counting reds in the black-height.** Black-height counts only black nodes; including reds destroys the well-definedness that makes the whole proof work, since red counts differ per path. - **Counting the node itself.** Convention excludes x from `bh(x)`; being sloppy here shifts the bound by one and confuses the induction. - **Forgetting the root-is-black rule.** Without it, step 2's "at least half" argument is slightly weaker at the top of the path. It is a convenience rule — a red root can always be repainted black without changing any path's black count — but it keeps the accounting clean. - **Reporting the bound as `log2 n`.** The whole point of the derivation is the factor of two. A candidate who states the bound without it has skipped the step that distinguishes this family from a strictly height-balanced one. - **Reading `2·log n` as the observed depth.** It is an upper bound on the worst legal shape, not an estimate of the tree you will actually build.
- Why is the bound written with log2(n+1) rather than plain log2 n?Because the size lemma gives `2^b − 1` internal nodes, not `2^b`. Starting from `n >= 2^(h/2) − 1` you add one before taking the logarithm, which yields `h <= 2·log2(n+1)`. The `+1` is the empty-sentinel bookkeeping; asymptotically it changes nothing, but it is the difference between a proof and a hand-wave.
- Would the height bound survive if a red root were allowed?Yes. Path black counts are unaffected by the root's color, and a red root can always be repainted black without violating any rule, since that adds one black to every path equally. The black-root convention exists to simplify the repair procedure's top case, not to make the height argument work.
- How would the bound change if two consecutive red nodes were permitted?It would loosen to roughly `3·log2 n`. With reds allowed in pairs, each black could be padded by two reds, so blacks would be guaranteed only a third of a path rather than half, and the black-height would drop to about `h/3`. The no-red-red rule is exactly what sets the constant to 2.
saying these in an interview costs you the question
- Includes red nodes when computing black-height
- States the height bound as log2 n, dropping the factor of two
- Claims black-height equals the tree's height
- Cannot say why blacks are at least half of any path
- Confuses the minimum node count with a maximum