Wiki
Advanced15 min read

Trees, BSTs and AVL rotations

A binary search tree orders linked nodes so each comparison halves the search — if it stays balanced, which is what rotations buy.

A linked list is a line; a tree branches. Give each node two children and impose one ordering rule — smaller values left, larger values right — and you get a structure where each comparison discards half the remaining candidates. That is the same logarithmic leap binary search gave us, but achieved through pointers rather than a sorted array.

The BST invariant does the work

At every node, everything in the left subtree is smaller and everything in the right subtree is larger. Lookup, insertion and deletion all navigate by comparing once per level. The only question is how many levels there are.

Insert values below, first with balancing off, then on. Watch the height and the balance factors change.

Insert values — turn balancing on to keep the tree shallow

Empty tree. Insert a value.

height

0 (nodes 0)

in-order traversal

—

rotations

—

Insert 1, 2, 3, 4 with balancing off: the tree is a chain and height grows linearly. Turn balancing on and each insertion checks the balance factor (+1 / 0 / -1 is fine, ±2 triggers a rotation) and restores logarithmic height. The circled balance factor is height(left) − height(right).

The binary search tree

A BST node holds a value and two child references. Search is a walk:

def search(node, target):
    while node is not None:
        if target == node.value:
            return True
        node = node.left if target < node.value else node.right
    return False

Its cost is the tree's height hh, not its size. A balanced tree has h≈log⁡2nh \approx \log_2 n; a degenerate one has h=nh = n and behaves exactly like a linked list.

The three depth-first traversals visit nodes in different orders:

  • In-order (left, node, right) yields values in sorted order — the invariant made visible.
  • Pre-order (node, left, right) is useful for copying a tree.
  • Post-order (left, right, node) is useful for freeing or evaluating it.

Why rotations exist

Insert sorted data — 1, 2, 3, 4, 5 — into a naive BST and every new value goes to the right, producing a chain of height nn. The tree has not become wrong, just slow. AVL trees fix it by keeping heights balanced:

  • Each node stores its balance factor = height(left) − height(right).
  • A valid AVL node has a balance factor of −1, 0 or +1.
  • After an insertion makes some balance factor ±2, a rotation restores it.

There are four cases: left-left and right-right need a single rotation; left-right and right-left need two. A rotation rearranges three pointers and preserves the in-order sequence, so the BST invariant survives.

Rotation is local but its effect is global

A rotation only touches a few pointers, but it changes the height of the rotated subtree, which can ripple up the path to the root. AVL insertion therefore rebalances on the way back up from the new leaf, not just at the point of insertion.

Red-black trees are the other common self-balancing family; they allow slightly more imbalance in exchange for fewer rotations on update. Python's standard library exposes neither directly, but the same ideas live inside dict and sortedcontainers.

Illustrative vs real

The panel keeps a small tree so each rotation is legible. Large AVL trees store heights or balance factors per node and rebalance during deletion as well as insertion. The guarantee — height stays within a constant factor of log⁡2n\log_2 n, so search is O(log⁡n)O(\log n) — is exactly what the balance factor is there to maintain.

Check yourself

Eduspheria wiki · Programming & Data Structures, Data structures

0 / 5 answered

  1. 1Which traversal of a BST visits the values in sorted order?
    Multiple choice
  2. 2Inserting sorted values into a naive BST produces a balanced tree.
    True / false
  3. 3What is the balance factor of a node whose left subtree has height 4 and right subtree has height 2?
    Numeric answer
  4. 4What operation restores an AVL tree's balance when a node becomes unbalanced?
    Short answer
  5. 5What is the worst-case search time in a balanced BST of n nodes?
    Multiple choice

From the exam paper

Modeled on NITJ AI-507, End-Sem December 2024

0 / 4 answered

  1. 1A binary tree has preorder bcefdgh and inorder ecfbgdh. Give its postorder traversal as one lowercase string.
    Short answer
  2. 2In the tree reconstructed from preorder bcefdgh and inorder ecfbgdh, which node is the root?
    Multiple choice
  3. 3In that same tree, which two nodes are the left and right children of the root b?
    Multiple choice
  4. 4How many leaf nodes does the reconstructed tree contain?
    leaves
    Numeric answer

Where next: heaps — a tree with a weaker order that still keeps the extreme element at hand.