What do a red-black tree's color invariants guarantee, and is the tree perfectly balanced?
answer
- one extra bit stored per node
- count only the black nodes on a path
- reds are not allowed to stack
- longest path versus shortest path
- bounded height, not equal heights
basics
~20 sRed-black rules — no red node has a red child, and every root-to-leaf path crosses equally many black nodes — cap height near 2·log n. That is bounded, not perfectly balanced: one branch may be twice as deep as another.
solid answer
~40 sA red-black tree is an ordinary binary search tree where every node carries one extra bit of color. The invariants are: the root is black, every leaf sentinel is black, both children of a red node are black, and every path from a given node down to the sentinels below it crosses the same number of black nodes. That last rule fixes a common `black-height` for all paths; the no-red-red rule then limits how much red can pad a path, so the longest root-to-leaf path is at most twice the shortest. Height is therefore O(log n), and search, insert and delete are O(log n) worst case. It is a bound, not perfection — the tree never tries to equalize branch lengths, and colors are metadata that play no part in the search itself.
go deeper
Recall the invariants and what they buy: worst-case O(log n) search, insert and delete. Be able to state that the longest root-to-leaf path is at most twice the shortest.
Explain why equal black counts plus the no-red-red rule bound the height, and make clear that colors are bookkeeping that never affects key ordering or search results.
Say what the guarantee is worth in production: a predictable worst case against sorted or adversarial input, paid for with an extra bit per node and pointer writes on update.
Own the framing that this is a bound, not a shape. Any structure whose worst case your design leans on should come with a stated bound you can defend and a known per-write cost.
## The structure A red-black tree is a binary search tree first and a colored tree second. Every node holds a key; everything in its left subtree compares smaller, everything in its right subtree compares larger. On top of that, each node carries a single extra bit: red or black. A lookup ignores the bit entirely — it walks left or right purely by comparing keys. The colors exist only so the tree can cheaply detect and repair a bad shape after an insertion or a deletion. ## The invariants 1. Every node is red or black. 2. The root is black. 3. Every leaf is black. "Leaf" here means the empty sentinel positions hanging below the real nodes, not the bottom-most keys. 4. A red node's children are both black — equivalently, no two red nodes are adjacent along any path. 5. For every node, all downward paths from it to the sentinels below cross the same number of black nodes. Rule 5 is the load-bearing one, and it is the one people misread. It does **not** say every path has the same length. It says every path has the same *black* length. That shared count is the node's **black-height**. ## Why this bounds the height Consider the shortest root-to-leaf path. In the extreme it is all black, say `b` nodes long, so the tree's black-height is `b`. Now consider the longest path. By rule 5 it must also contain exactly `b` black nodes. By rule 4 it cannot contain two reds in a row, so between and around those blacks it can hold at most one red per black — at most `b` reds. So the longest path holds at most `2b` nodes: **the longest root-to-leaf path is at most twice the shortest**. Counting nodes downward from that observation gives the standard result, height at most about `2·log2(n+1)`. Contrast the two failure modes this sits between. An unconstrained binary search tree fed already-sorted keys degenerates into a chain of n nodes, and every operation becomes O(n). A *perfectly* balanced tree — all leaves at the same depth — only exists at sizes `2^k − 1` and would need wholesale restructuring after most insertions. Red-black rules deliberately allow a range of shapes, and that slack is exactly what makes updates cheap. ## What the guarantee buys, and what it costs It buys worst-case O(log n) search, insert, delete, predecessor and successor, plus ordered traversal in O(n) — and "worst-case" is the point. Unlike a plain search tree, no insertion order, adversarial or merely sorted, can degrade it. It costs one bit per node (usually free, packed into a spare bit of a pointer or an existing word), a handful of pointer writes when a rebalance rotates, and the general locality penalty of a pointer-linked structure versus a contiguous array. Note that recoloring changes no pointers at all, and rotations — although they move pointers — preserve the in-order key sequence exactly. Colors are metadata: they can never move a key to the wrong side of a comparison. ## The misconceptions this question aims at **"Balanced means both subtrees have the same height."** No structure in practical use demands that. Even the stricter self-balancing family only bounds the difference of the two subtree heights by one; red-black trees do not constrain subtree heights directly at all. They constrain black counts, and let actual heights differ by up to a factor of two. **"Every root-to-leaf path has the same number of nodes."** Only the black nodes are counted. A path with three blacks and three reds and a path with three blacks and no reds coexist happily in one valid tree. **"So a lookup does exactly log2 n comparisons."** The bound is `O(log n)` with a worst-case constant of about 2. A real tree is usually far closer to `log2 n` than to `2·log2 n`, but the guarantee you may lean on in a design argument is the bound, not the typical case. **"Red nodes are the ones being rebalanced" / "colors guide the search."** They do not. A search executes identically on a red-black tree and on the same tree with all colors erased. One useful sanity check: a tree in which every node is black and all leaves sit at the same depth satisfies all five rules. So does a tree where every second level is red. Both are legal; the rules describe an envelope of shapes, not one shape.
- Why is one color bit per node enough — why not store each subtree's height instead?Storing heights needs several bits and forces an update along the whole path to the root on every change, plus a recomputation whenever a subtree shifts. One color bit plus purely local rules delivers the same O(log n) height guarantee with repairs that are usually local and often touch no pointers at all. The bit also fits in space most node layouts already waste.
- What would you get if every path were required to hold the same total number of nodes?A perfect tree — which only exists when the size is one less than a power of two, and which most insertions would break, forcing a global restructure. Relaxing the requirement to equal black counts keeps the height logarithmic while letting a single insertion be repaired with O(1) structural work in the common case.
- Can recoloring a node change which keys the tree will find?No. Colors are metadata and searching never reads them, so recoloring cannot affect any lookup result. Rotations do move pointers, but a rotation is defined to preserve the in-order sequence of keys, so it too leaves every search answer unchanged. Only inserting or deleting a key changes what the tree contains.
Think of a dress code that says every route through the building must pass the same number of security desks, and no two unstaffed doors in a row. Routes still differ in length — they are just kept from getting wildly long.
saying these in an interview costs you the question
- Says balanced means both subtrees have equal height
- Claims every root-to-leaf path holds the same number of nodes
- Thinks the colors influence where a key is stored or searched
- Promises exactly log2 n comparisons per lookup
- Counts red nodes when asked for the black-height