Red-Black Tree Visualization for Coding Interviews
Recolor + rotate cases; every path has equal black-height.
Concept
A red-black tree is a binary search tree that tags every node with a color - red or black - and enforces five invariants so that the longest root-to-leaf path is at most twice the length of the shortest. That looser bound compared to AVL means lookups are slightly slower, but the amortized number of rotations per update is smaller, which is why red-black trees underlie Java's TreeMap, C++ std::map, and the Linux kernel's CFS scheduler. The five CLRS invariants are: every node is red or black; the root is black; every NIL leaf is black; no red node has a red child; every root-to-leaf path has the same number of black nodes (the black-height). The last two together imply the 2x height bound. Most implementations use a shared sentinel NIL node to stand in for every null child, which simplifies color bookkeeping because NIL is always black and you never have to null-check before reading a color.
How it works
Insert starts with a plain BST insert and colors the new node red, because coloring it black would immediately violate the equal-black-height property. The only invariant that can now be broken is the no-red-red rule. Fix-up walks up from the new node and handles three cases by looking at the uncle (the sibling of the parent). Case 1: the uncle is red - recolor parent and uncle to black, recolor grandparent to red, then move the pointer up to the grandparent and repeat. Case 2: the uncle is black and the new node is the inner child (left-right or right-left shape) - rotate the parent to convert it into case 3. Case 3: the uncle is black and the new node is the outer child - recolor parent to black, grandparent to red, and rotate the grandparent. Delete is structurally similar but harder, because removing a black node reduces the black-height of one subtree. The fix-up pushes a conceptual extra-black token up the tree and eliminates it via four mirrored cases that look at the sibling's color and the colors of the sibling's children. All operations run in O(log n) with at most three rotations per insert and four per delete, which is why red-black is the default balanced BST in most standard libraries.
Implementation
public class RedBlackTree {
private static final boolean RED = true, BLACK = false;
static class RBNode {
int key;
boolean color;
RBNode left, right, parent;
RBNode(int key, boolean color) { this.key = key; this.color = color; }
}
private final RBNode NIL = new RBNode(0, BLACK);
private RBNode root = NIL;
public void insert(int key) {
RBNode z = new RBNode(key, RED);
z.left = z.right = z.parent = NIL;
RBNode y = NIL, x = root;
while (x != NIL) { y = x; x = key < x.key ? x.left : x.right; }
z.parent = y;
if (y == NIL) root = z;
else if (key < y.key) y.left = z; else y.right = z;
insertFixUp(z);
}
private void insertFixUp(RBNode z) {
while (z.parent.color == RED) {
RBNode g = z.parent.parent;
if (z.parent == g.left) {
RBNode y = g.right; // uncle
if (y.color == RED) { // case 1: recolor
z.parent.color = BLACK; y.color = BLACK; g.color = RED; z = g;
} else {
if (z == z.parent.right) { z = z.parent; leftRotate(z); } // case 2
z.parent.color = BLACK; z.parent.parent.color = RED; // case 3
rightRotate(z.parent.parent);
}
} else {
RBNode y = g.left;
if (y.color == RED) {
z.parent.color = BLACK; y.color = BLACK; g.color = RED; z = g;
} else {
if (z == z.parent.left) { z = z.parent; rightRotate(z); }
z.parent.color = BLACK; z.parent.parent.color = RED;
leftRotate(z.parent.parent);
}
}
}
root.color = BLACK;
}
private void leftRotate(RBNode x) {
RBNode y = x.right;
x.right = y.left;
if (y.left != NIL) y.left.parent = x;
y.parent = x.parent;
if (x.parent == NIL) root = y;
else if (x == x.parent.left) x.parent.left = y; else x.parent.right = y;
y.left = x; x.parent = y;
}
private void rightRotate(RBNode y) {
RBNode x = y.left;
y.left = x.right;
if (x.right != NIL) x.right.parent = y;
x.parent = y.parent;
if (y.parent == NIL) root = x;
else if (y == y.parent.right) y.parent.right = x; else y.parent.left = x;
x.right = y; y.parent = x;
}
}Complexity
- Search:
O(log n) - Insert:
O(log n) - Delete:
O(log n) - Space:
O(n)
Common pitfalls
- Forgetting to set the root to black after insertFixUp - it is the one place the invariant is only restored at the very end.
- Using null children instead of a NIL sentinel - every color check then needs a null guard and it is easy to miss one.
- Mixing up the outer vs inner case in fix-up: the inner case needs a pre-rotation to turn it into the outer case.
- Skipping the symmetric branch (parent is right child of grandparent) - omitting it silently corrupts the tree on alternate insertions.
- Rotating without updating parent pointers both on the moved nodes and on their former parent, leaving the tree disconnected.
Key design decisions & trade-offs
- Red-black vs AVL — Chosen: Red-black when updates are frequent. Looser height bound allows fewer rotations per update at the cost of slightly taller trees and slightly slower lookups.
- Null handling — Chosen: Shared NIL sentinel. Every pointer is non-null, so color reads never need a null guard and the fix-up code stays symmetric.
- Parent pointers — Chosen: Store an explicit parent field. Insert fix-up walks up the tree repeatedly; threading through parents is cheaper and clearer than maintaining a path stack.
Practice problems
Interview follow-ups
- Implement delete with the four fix-up cases on the extra-black token.
- Benchmark red-black inserts against AVL on a uniform random workload.
- Read the TreeMap implementation in the JDK and compare with CLRS pseudocode.
- Augment the tree with subtree size to support rank and select in O(log n).
- Swap color bit into the low bit of the parent pointer to save one byte per node.
Why it matters
Red-Black Tree is a core part of the Trees toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".