What Is a Tree Rotation? The Pointer Swap That Keeps BSTs Fast
- Tree rotations are O(1) local pointer swaps that fix BST imbalance without breaking the sorted in-order traversal invariant
- Left rotation promotes the right child to root; right rotation does the opposite — each reassigns exactly 3–4 pointers
- Four imbalance cases: Left-Left and Right-Right need one rotation; Left-Right and Right-Left require a double rotation
- AVL trees rotate after any height imbalance greater than 1; Red-Black trees mix rotations with color flips for fewer writes on write-heavy workloads
- Interview signal: explain why a sorted BST insertion degrades to O(n), how rotations restore O(log n), and when to prefer AVL vs Red-Black
Insert the numbers 1, 2, 3, 4, 5 into a BST in that order. Here's what you get:
1
\
2
\
3
\
4
\
5
That's not a tree. That's a linked list wearing a tree's name tag. Search is O(n). Everything the BST promised you is gone, and you gave it the most reasonable-seeming input you could have.
Tree rotations are the fix. A rotation is a local restructuring of a subtree that changes its shape while leaving the BST ordering intact. It runs in O(1) time and uses O(1) extra space. Self-balancing trees like AVL and Red-Black trees call them automatically after insertions and deletions to keep height at O(log n).
The One Rule It Cannot Break
A binary search tree is defined by one invariant: for any node, every value in its left subtree is smaller, and every value in its right subtree is larger.
The in-order traversal of a BST always produces a sorted sequence, and a rotation cannot change that sequence. The nodes appear in the same sorted order before and after. Only the pointers are different.
Keep that rule in mind and the mechanics stop looking arbitrary. Every step follows from it.
Left Rotation: Three Pointer Assignments
Start with this subtree:
X
/ \
A Y
/ \
B C
X is the root. Y is X's right child. A, B, and C are sub-subtrees (they could be single nodes, full subtrees, or empty).
A left rotation on X produces:
Y
/ \
X C
/ \
A B
Y is the new root. X dropped to become Y's left child. B, which was Y's left subtree, moved to become X's right child. A and C didn't move at all.
In-order traversal before: A ... X ... B ... Y ... C. After: A ... X ... B ... Y ... C. Identical. The BST property holds.
def rotate_left(x): y = x.right # y is the new root b = y.left # B is the subtree that moves y.left = x # x becomes y's left child x.right = b # B becomes x's right child update_height(x) update_height(y) return y # return new root to caller
Three pointer assignments. That's the whole operation. You've probably written more pointer manipulation by accident in a function that was supposed to be read-only.
Right Rotation: The Mirror
A right rotation on Y is the left rotation run in reverse:
Y X
/ \ => / \
X C A Y
/ \ / \
A B B C
def rotate_right(y): x = y.left b = x.right x.right = y y.left = b update_height(y) update_height(x) return x
B is again the subtree that migrates, and in-order traversal is preserved. Same logic, opposite direction. If you understood left rotation, you get right rotation free.
Four Ways a Tree Can Go Wrong
Single rotations fix two of the four imbalance shapes. The other two need a double rotation: rotate once to reduce to a single-rotation case, then rotate again. Trees fail in exactly four flavors.
Left-Left: Single Right Rotation
Z Y
/ / \
Y => X Z
/
X
Heavy on the left-left. One right rotation on Z restores balance.
Right-Right: Single Left Rotation
Z Y
\ / \
Y => Z X
\
X
Heavy on the right-right. One left rotation on Z.
Left-Right: Double Rotation (Left, Then Right)
Z Z Y
/ / / \
X => Y => X Z
\ /
Y X
Heavy on the left, but the left child leans right. A single right rotation on Z would make things worse before they got better. Rotate left on X first to convert to the Left-Left case, then rotate right on Z.
def rotate_left_right(z): z.left = rotate_left(z.left) return rotate_right(z)
Right-Left: Double Rotation (Right, Then Left)
Z Z Y
\ \ / \
X => Y => Z X
/ \
Y X
Rotate right on X, then left on Z.
def rotate_right_left(z): z.right = rotate_right(z.right) return rotate_left(z)
The double rotation cases feel backward the first time you see them. You rotate in the wrong direction on purpose, because the zigzag shape has to be straightened before the outer rotation will work. It's like unfolding a bent straw before you blow through it.
Why Rotations Are O(1): No Subtrees Are Touched
A rotation only reassigns pointers between three nodes. The subtrees A, B, and C travel as whole units without any internal modifications.
It doesn't matter if subtree B contains one node or ten million. The rotation changes exactly the same three or four pointers. O(1) time, no extra memory.
This is what makes self-balancing BSTs practical. An insertion might check the balance factor at every ancestor up to the root, O(log n) nodes. But each rotation along the way is O(1). Total insertion cost stays O(log n).
Where Rotations Show Up in Real Code
Rotations are the primitive operation for two families of self-balancing trees, and those trees are everywhere.
AVL trees maintain a strict balance invariant: for every node, the heights of its left and right subtrees differ by at most one. After each insertion or deletion, the tree checks the balance factor (height_left minus height_right) walking back up to the root. If any node reaches a factor of plus-two or minus-two, one of the four cases above fires. AVL height is bounded by 1.44 log n, guaranteeing tight O(log n) operations.
Red-Black trees add a color bit to each node and enforce looser rules: all paths from root to leaf have equal numbers of black nodes, and no two consecutive red nodes appear. Fixing violations after an insertion or deletion involves a mix of rotations and color flips. Red-Black trees allow slightly more imbalance than AVL trees, so they do fewer rotations on average during updates, at the cost of marginally slower lookups in the worst case.
The practical result: Java's TreeMap and TreeSet, C++'s std::map and std::set, and the Linux kernel's scheduler all run on Red-Black trees. Every time you call map.get() and it returns in O(log n), a rotation or two got it there at some point during a prior insertion. Totally silent. Totally invisible. You've benefited from this mechanism thousands of times without a single thought about it.
Tree Rotation Interview Questions: What Gets Asked
You will almost never be asked to implement a full AVL or Red-Black tree in an interview. That's a multi-hour project. If an interviewer actually asks for it, you're either at a very specific kind of company or somebody misread the time slot.
What they actually ask:
"Why can a BST degrade to O(n)?" Sketch the sorted-insertion example. Explain that without a balancing mechanism, height grows to O(n) in the worst case. The interviewer is checking whether you know a BST is only as good as its balance.
"What makes a balanced BST balanced?" This is the rotation question. Rotations are local O(1) pointer changes that maintain BST order while reducing height. Self-balancing trees call them automatically.
"When do you use a BST instead of a hash map?" When you need ordered operations: range queries, floor and ceiling lookups, in-order iteration. Rotations are what keep those operations at O(log n) rather than O(n). A hash map can't answer "give me all keys between 100 and 200." A balanced BST can.
At more senior levels or in systems roles, interviewers may probe the AVL versus Red-Black tradeoff: AVL for read-heavy workloads because the stricter balance means faster lookups, Red-Black for write-heavy because fewer rotations per update. Knowing the distinction by name puts you ahead of candidates who can only say "balanced BSTs exist."
If you want to practice explaining this kind of structural reasoning out loud under actual time pressure, SpaceComplexity runs voice-based DSA mock interviews with follow-up questions on exactly this kind of topic, not just whether you produced the right answer.
The One Intuition Worth Keeping
A rotation is the minimal edit that fixes a local violation of a tree's balance constraint.
The key insight: the in-order traversal never changes, so the BST is still a BST after the rotation. Only the structural shape changes. The node that was a root becomes a child. A subtree that was on one side moves to the other. But if you listed all the values in sorted order before and after, the list is identical.
Everything else, the four cases, the double rotations, the color flips in Red-Black trees, falls out from that one invariant.