skip to content

Why does a single rotation fail to rebalance an AVL tree after a zig-zag insertion?

level: middleimportance: must knowfreq 62%

answer

  1. two shapes: straight and bent
  2. which subtree does the rotation hand over
  3. the middle grandchild is the tall one
  4. the imbalance flips sign instead of vanishing
  5. fix the child first, then the parent

basics

~20 s

In a zig-zag insertion the tall subtree sits in the middle of the path, so a single rotation just hands it across and leaves a mirror-image imbalance. Two rotations — the child first, then the unbalanced node — fix it.

solid answer

~50 s

Insertions come in two shapes. In a zig-zig (straight) shape the new key goes into the *outer* grandchild, and one rotation at the unbalanced node lifts the whole heavy side up a level. In a zig-zag shape the new key goes into the *inner* grandchild, and a single rotation just swaps which side is heavy: the middle subtree it hands over is exactly the tall one, so you end up two levels out of balance in the other direction. Concretely, insert 30, 10, 20 into an empty tree: a right rotation at the root yields 10 with the chain 30 -> 20 below it, still a factor of -2. The repair is a **double rotation**: rotate the child (left at 10) so the zig-zag becomes a zig-zig, then rotate the unbalanced node (right at 30). The inner grandchild becomes the new subtree root, and both original nodes become its children.

code

pseudocode · 10 lines
pseudocode
// z = lowest node with |balance(z)| > 1 after an insertion
y = taller_child(z)

if balance(z) > 1:                // z is left-heavy, y is z's left child
    if balance(y) >= 0:           // zig-zig (LL): y's taller child is on the left
        rotate_right(z)
    else:                         // zig-zag (LR): y's taller child is on the right
        rotate_left(y)
        rotate_right(z)
...                               // mirror cases when balance(z) < -1

go deeper

for a junior

Know that rotations come in single and double forms and that the double one is needed when the insertion path bends. Being able to draw a three-node example and name the two rotations is enough at this level.

for a middle

Trace the zig-zag case on a whiteboard, show that a single rotation flips the imbalance instead of removing it, and explain that the rotation hands over precisely the subtree the insertion made tall.

for a senior

Reason about which node to repair (the lowest violator), argue that the repaired subtree returns to its pre-insertion height, and explain why every rotation must re-parent the middle subtree rather than drop it.

for a principal

Own the framing that rotations are cheap local restructuring with a global guarantee, and be able to say what a team gives up by hand-rolling this instead of using a vetted ordered structure — rebalance code is small, subtle, and expensive to debug in production.

## Rotations, and what they promise A rotation is a constant-time relinking of two adjacent nodes that **preserves the in-order sequence of keys** and changes only the shape. A right rotation at node `z` whose left child is `y` makes `y` the subtree root, makes `z` its right child, and hands `y`'s former right subtree to `z` as its new left child. Every key that was less than `z` still is; the search property survives. That is the whole reason rotations are a legal tool — they buy height without touching ordering. ## Four cases, two shapes After an insertion, let `z` be the **lowest** node whose balance factor has reached magnitude 2, `y` its taller child and `x` `y`'s taller child. The path `z -> y -> x` has one of four shapes, conventionally named by the directions taken: LL, RR, LR, RL. LL and RR are *zig-zig* — both steps go the same way — and LR and RL are *zig-zag*. The zig-zigs need one rotation; the zig-zags need two. ## Why one rotation is not enough on a zig-zag Think about which subtree the single rotation actually relocates. A right rotation at `z` moves `y`'s **right** subtree across to become `z`'s left subtree. In the LL case, `y`'s right subtree is the short one, and moving it under `z` — which just lost its whole left side to `y` — evens both nodes out. In the LR case, `y`'s right subtree is `x`'s subtree, the *tall* one, the one the insertion just grew. So the rotation takes the excess height off `y`'s side and deposits all of it under `z`. `z` is now the right child of `y` and is two levels taller than `y`'s left side: the same magnitude-2 violation, mirrored. The smallest example is three nodes. Insert 30, then 10, then 20 into an empty tree. The shape is root 30, left child 10, and 10's right child 20 — an LR zig-zag. Heights (leaf = 0, empty = -1): node 10 has height 1, node 30's right side is empty at -1, so `balance(30) = 1 - (-1) = 2`. Apply a right rotation at 30: node 10 becomes the root, 30 becomes its right child, and 10's former right subtree (the node 20) becomes 30's left child. Now the tree is 10 -> right 30 -> left 20, and `balance(10) = -1 - 1 = -2`. The violation did not go away; it changed sign. ## The double rotation, and why it works The fix is to *convert* the zig-zag into a zig-zig first. Rotate left at the child `y` (node 10): `x` (node 20) rises above it, giving the straight chain 30 -> 20 -> 10 with 10 on the outside. That is now an LL shape, so a right rotation at `z` (node 30) finishes it: node 20 becomes the root with 10 and 30 as children, every balance factor is 0, and the in-order sequence 10, 20, 30 is unchanged throughout. Generalising: after an LR double rotation, `x` — the inner grandchild, the one the insertion made tall — becomes the subtree root, `y` takes `x`'s left subtree as its new right subtree, `z` takes `x`'s right subtree as its new left subtree, and `y` and `z` become `x`'s two children. Whichever of `x`'s two subtrees the new key landed in, both `y` and `z` end up with one side of each height, so the rebalanced subtree is exactly as tall as it was *before* the insertion. It helps to see the double rotation as one operation, not two independent fixups: it is a single restructuring of a three-node, four-subtree cluster, and it is conventionally implemented and counted as one rebalancing step even though it relinks along two axes. Some presentations skip the two-rotation framing entirely and write it directly as a three-node restructure; the resulting shape is identical. ## Recognising the case in code You never need to look at keys to classify the case, only at signs. If `z` is left-heavy and its left child `y` is left-heavy or level, it is LL and one right rotation suffices. If `z` is left-heavy and `y` is *right*-heavy, the signs disagree and it is LR — rotate left at `y`, then right at `z`. The mirror rules cover RR and RL. After an insertion `y` is never level, but the `>= 0` form of the test is the one to memorise because deletion can produce exactly that case. ## Where hand-traces go wrong The two recurring errors are dropping the middle subtree — every rotation must re-parent it, never discard it — and rebalancing at the wrong node. Always fix the **lowest** violating node on the retrace path; repairing an ancestor first leaves the real violation buried below it and can leave the tree illegal even after a correct-looking rotation.

  • Do rotations ever change the answer a later search gives?
    No. A rotation re-parents three links so that the in-order traversal of the affected subtree is unchanged; every key that was on the left of a given node in sorted order still is. Only depths change, which is the point — the search property is invariant, the path lengths are not.
  • How do you tell LR from LL without looking at the keys?
    Compare signs. If the unbalanced node is left-heavy and its left child is also left-heavy (or level), the path is straight and one rotation fixes it. If the child leans the other way, the path bends and you need the double rotation. The same sign test, mirrored, distinguishes RR from RL.
  • Which node ends up as the root of the repaired subtree in a double rotation?
    The inner grandchild — the node on the bent step, the one the insertion made tall. It takes the two former path nodes as its children and distributes its own two subtrees between them, leaving the subtree at exactly its pre-insertion height.

Straightening a kinked hose: pulling on the end while the kink is in the middle just moves the kink to the other side. You have to straighten the kink first, then pull.

saying these in an interview costs you the question

  • Applies one rotation to a zig-zag and declares it balanced
  • Thinks a double rotation is the same rotation performed twice at one node
  • Says rotations can reorder keys or break the search property
  • Drops or discards the middle grandchild's subtree during the relink
  • Rebalances the highest violating node instead of the lowest

context

resolving links…