Intermediate · Module 13 · Lesson 5

Balanced BSTs

AVL and red-black invariants keep logarithmic height.

15–25 min readLesson 74 of 123

Lesson 74 of 123

1d streak

Balanced BSTs: Avoiding O(n) Degeneration via Rotations

If keys are inserted in sorted order [1, 2, 3, 4, 5], a naive BST degenerates into a skewed linked list where search, insertion, and deletion degrade from $O(log n)$ to O(n). Self-balancing trees (AVL and Red-Black trees) maintain a height of $O(log n)$ using tree rotations.

The Degeneration Problem vs Tree Rotationstext

Degenerate Skewed BST (Sorted Inserts):
   (1)
     \
     (2)
       \
       (3)        Height = 5 -> Search cost is O(n)!
         \
         (4)
           \
           (5)

Tree Rotation (Restoring Logarithmic Balance):
Right Rotation on Y:
        ( Y )                    ( X )
       /     \                  /     \
     ( X )    T3      --->     T1     ( Y )
    /     \                          /     \
   T1     T2                        T2     T3

Notice: Inorder order is strictly preserved: T1 < X < T2 < Y < T3!
Height is reduced from 2 to 1!

Balanced Tree Type	Balance Invariant	Lookup Speed	Insertion / Deletion Speed	Real-World Usage
AVL Tree	\|Height(Left) - Height(Right)\| ≤ 1	Faster (strictly balanced, height ≤ 1.44 log n)	Slower (more frequent rotations)	Read-heavy lookups (databases)
Red-Black Tree	No two consecutive red nodes; equal black depth	Slightly slower (height ≤ 2 log n)	Faster (at most 3 rotations on delete)	Java TreeMap, C++ std::map, Linux CFS

Cost Model

Complexity & Trade-offs

OperationTimeSpaceWhy

Search / update

O(log n)

O(n) stored

The bound follows from the number of states visited and the work performed per transition.

When to use it

Hierarchies, ordered sets/maps, expression trees, and recursive aggregation.
Path, ancestor, depth, and subtree questions.
Maintaining sorted dynamic data with balanced trees.

Common mistakes

Assuming a BST is balanced without a balancing guarantee.
Confusing node depth with subtree height.
Discarding information needed by the parent instead of returning it.

Practice prompts

Reproduce the worked Balanced BSTs example without looking at the trace.
Change one input condition and explain whether the Balanced BSTs invariant still holds.
Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.

Explain why every transition is safe.

Construct a worst-case input.

Name one alternative and its trade-off.