In a red-black tree insert fixup, what decides whether you recolor or rotate?

middlenice to knowfreq 32%

answer

look at the parent's sibling
one branch touches no pointers at all
the other branch ends the repair
the violation climbs two levels at a time
at most two rotations per insertion

basics

~20 s

The uncle's color decides. In a red-black tree insert fixup, a red uncle means recolor parent, uncle and grandparent and push the violation two levels up; a black or absent uncle means one or two rotations end the repair immediately.

solid answer

~50 s

A new key is inserted red, which can never break the black-count rule but may put a red node under a red parent. The repair looks at the uncle — the parent's sibling. If the uncle is red, you recolor: parent and uncle become black, the grandparent becomes red. Every path's black total is unchanged, no pointer moves, and the only possible remaining violation is now at the grandparent, so the loop restarts two levels higher. If the uncle is black or absent, recoloring cannot fix it without unbalancing black counts, so you rotate — one rotation if the new node is on the outside, two if it is on the inside — recolor the pivot, and the loop terminates. An insertion therefore performs at most two rotations, and the common case performs none at all.

A new key is inserted red, which can never break the black-count rule but may put a red node under a red parent. The repair looks at the **uncle** — the parent's sibling. If the uncle is red, you recolor: parent and uncle become black, the grandparent becomes red. Every path's black total is unchanged, no pointer moves, and the only possible remaining violation is now at the grandparent, so the loop restarts two levels higher. If the uncle is black or absent, recoloring cannot fix it without unbalancing black counts, so you rotate — one rotation if the new node is on the outside, two if it is on the inside — recolor the pivot, and the loop terminates. An insertion therefore performs at most two rotations, and the common case performs none at all.

code

pseudocode · 15 lines

pseudocode

// z is the newly inserted node, colored RED
while color(parent(z)) == RED:
    g = parent(parent(z))
    if parent(z) == left(g):
        u = right(g)                  // the uncle
        if color(u) == RED:           // recolor only, no pointer moves
            color(parent(z)) = BLACK
            color(u) = BLACK
            color(g) = RED
            z = g                     // violation climbs two levels
        else:                         // rotate at g (twice if z is inside)
            ...                       // then the loop ends
    else:
        ...                           // mirror of the above
color(root) = BLACK

go deeper

for a junior

Know that a new key is added red and that the repair is triggered only when its parent is also red. Naming the two outcomes, recolor or rotate, is enough here.

for a middle

Explain that the uncle's color selects the case, why the recolor case preserves black counts, and why it climbs two levels instead of finishing.

for a senior

Turn it into a cost argument: unbounded color writes but at most two rotations per insertion and three per deletion, so structural change is O(1) amortized per update.

for a principal

Own the design principle behind it — insert red so the violation stays local and cheap, and prefer repairs that write metadata over repairs that move pointers when writes are the scarce resource.

Why insert red at all

A newly inserted node goes in red. That choice is deliberate: adding a black node would immediately break the invariant that all downward paths carry the same black count, and that rule is expensive to repair because it is global to a subtree. Adding a red node preserves black counts exactly and can only violate the local rule that no red node has a red child. Local violations are cheap. The whole repair procedure is an exercise in trading a global problem for a local one.

So after the ordinary search-tree insertion, exactly one thing can be wrong: the new node is red and its parent is red.

The uncle is the decision variable

Let z be the offending red node, p its red parent, g the grandparent (necessarily black, since p is red and the tree was legal before), and u the uncle — g's other child, that is p's sibling. Only u's color matters.

Uncle red. Recolor p and u black, and g red. Count blacks on any path through g: you added one black below (at p or u) and removed one at g, so every path's black total is unchanged — the global rule survives untouched. No pointers move; this is a few bit writes. But g is now red, and if g's parent is also red the same violation reappears one level up. So set z = g and repeat. Each iteration climbs two levels, so the loop runs at most about half the height, O(log n) times, each iteration O(1) and rotation-free.

Uncle black or absent. Now recoloring cannot work: blackening p without blackening u would give p's side an extra black that u's side does not get. The subtree must be reshaped instead. If z is on the same side as p relative to g (the "outside" case), one rotation at g plus a color swap between p and g fixes it. If z is on the inside, first rotate at p to convert it into the outside case, then do the outside fix — two rotations total. After either, the subtree root is black, so no red-red pair can propagate upward and the loop terminates.

Finally the root is forced black, which is always safe: it adds one black to every path equally.

The cost picture

	rotations	color writes	terminates?
Uncle red	0	3 per step	no — climbs two levels
Uncle black, outside	1	2	yes
Uncle black, inside	2	2	yes

So a single insertion performs at most two rotations, ever, regardless of tree size — the unbounded part of the work is color writes, which touch no pointers. Deletion is messier: removing a black node does break the black-count rule, and the repair carries a "double black" deficit upward until it can be discharged; that procedure needs at most three rotations. Amortized over a sequence of updates, both operations do O(1) structural change.

This is the property people mean when they say the coloring buys cheap writes. The O(log n) search for the insertion point still dominates; what the coloring avoids is O(log n) pointer surgery per update.

Reading the mirror case

Every case above has a mirror image, obtained by swapping left and right throughout. Implementations write one branch and mirror it, which is why the case tables look twice as long as the ideas in them. Being asked to enumerate all six cases from memory is unusual; being asked what the uncle's color decides, and why the red-uncle case does not terminate, is the normal interview depth.

Common wrong answers

"Every insertion rotates." Most do not. On randomly ordered keys the majority of insertions are either clean or repaired by recoloring alone.
"You look at the new node's sibling." The new node's sibling is a sentinel; it carries no information. The parent's sibling is the node that decides whether black counts can be preserved by recoloring.
"Recoloring changes a path's black count." In the red-uncle case it provably does not, which is exactly why it is legal. If it did, the repair would be no cheaper than the problem.
"The fixup can rotate O(log n) times." The loop iterates up to O(log n) times, but every iteration that loops is rotation-free, and the first iteration that rotates is the last.
"Insert the node black to avoid the red-red problem." That swaps a cheap local violation for an expensive global one.

## Why insert red at all A newly inserted node goes in red. That choice is deliberate: adding a **black** node would immediately break the invariant that all downward paths carry the same black count, and that rule is expensive to repair because it is global to a subtree. Adding a **red** node preserves black counts exactly and can only violate the local rule that no red node has a red child. Local violations are cheap. The whole repair procedure is an exercise in trading a global problem for a local one. So after the ordinary search-tree insertion, exactly one thing can be wrong: the new node is red and its parent is red. ## The uncle is the decision variable Let z be the offending red node, p its red parent, g the grandparent (necessarily black, since p is red and the tree was legal before), and u the **uncle** — g's other child, that is p's sibling. Only u's color matters. **Uncle red.** Recolor p and u black, and g red. Count blacks on any path through g: you added one black below (at p or u) and removed one at g, so every path's black total is unchanged — the global rule survives untouched. No pointers move; this is a few bit writes. But g is now red, and if g's parent is also red the same violation reappears one level up. So set z = g and repeat. Each iteration climbs two levels, so the loop runs at most about half the height, `O(log n)` times, each iteration `O(1)` and rotation-free. **Uncle black or absent.** Now recoloring cannot work: blackening p without blackening u would give p's side an extra black that u's side does not get. The subtree must be reshaped instead. If z is on the same side as p relative to g (the "outside" case), one rotation at g plus a color swap between p and g fixes it. If z is on the inside, first rotate at p to convert it into the outside case, then do the outside fix — two rotations total. After either, the subtree root is black, so no red-red pair can propagate upward and **the loop terminates**. Finally the root is forced black, which is always safe: it adds one black to every path equally. ## The cost picture | | rotations | color writes | terminates? | |---|---|---|---| | Uncle red | 0 | 3 per step | no — climbs two levels | | Uncle black, outside | 1 | 2 | yes | | Uncle black, inside | 2 | 2 | yes | So a single insertion performs **at most two rotations**, ever, regardless of tree size — the unbounded part of the work is color writes, which touch no pointers. Deletion is messier: removing a black node does break the black-count rule, and the repair carries a "double black" deficit upward until it can be discharged; that procedure needs **at most three rotations**. Amortized over a sequence of updates, both operations do O(1) structural change. This is the property people mean when they say the coloring buys cheap writes. The `O(log n)` search for the insertion point still dominates; what the coloring avoids is `O(log n)` *pointer surgery* per update. ## Reading the mirror case Every case above has a mirror image, obtained by swapping left and right throughout. Implementations write one branch and mirror it, which is why the case tables look twice as long as the ideas in them. Being asked to enumerate all six cases from memory is unusual; being asked what the uncle's color decides, and why the red-uncle case does not terminate, is the normal interview depth. ## Common wrong answers - **"Every insertion rotates."** Most do not. On randomly ordered keys the majority of insertions are either clean or repaired by recoloring alone. - **"You look at the new node's sibling."** The new node's sibling is a sentinel; it carries no information. The parent's sibling is the node that decides whether black counts can be preserved by recoloring. - **"Recoloring changes a path's black count."** In the red-uncle case it provably does not, which is exactly why it is legal. If it did, the repair would be no cheaper than the problem. - **"The fixup can rotate O(log n) times."** The loop iterates up to O(log n) times, but every iteration that loops is rotation-free, and the first iteration that rotates is the last. - **"Insert the node black to avoid the red-red problem."** That swaps a cheap local violation for an expensive global one.

Why does the red-uncle case move the violation upward instead of settling it?
Because turning the grandparent red is what keeps every path's black total unchanged — but that grandparent may itself sit under a red parent, recreating the same red-red pair two levels up. The repair therefore restarts from the grandparent, up to O(log n) times, with each step costing three color writes and no rotation.
How many rotations can a red-black deletion need, and why more than an insertion?
At most three. Deletion can physically remove a black node, which breaks the equal-black-count rule rather than just the red-red rule. The repair carries that deficit upward and has an extra terminating case that needs one more rotation than any insertion case does. Insertion never breaks black counts, so it stays at two.
Is the fixup loop's O(log n) worst case a practical concern?
Rarely. The looping iterations only write color bits, rotations are bounded by two per insertion, and the search for the insertion point already costs O(log n) with pointer chasing that dominates. Structural change is O(1) amortized per update, which is the property that makes this family attractive for write-heavy ordered indexes.

saying these in an interview costs you the question

Says every insertion requires at least one rotation
Inspects the new node's sibling instead of the parent's sibling
Claims the recolor case changes some path's black count
Thinks the fixup can perform O(log n) rotations per insert
Suggests inserting the new node black to avoid red-red pairs

In a red-black tree insert fixup, what decides whether you recolor or rotate?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

Why insert red at all

The uncle is the decision variable

The cost picture

Reading the mirror case

Common wrong answers

▾common follow-ups3 questions

▾red flags5 flags

§ context

▾related questions5 questions

▾related topics3 topics

Why insert red at all

The uncle is the decision variable

The cost picture

Reading the mirror case

Common wrong answers

answer

go deeper

context