Prerequisite:

Trees are graphs with no cycles and a designated root. They power everything from file systems to database indices to the priority queues inside shortest-path algorithms. This post covers binary tree traversals, BST operations, self-balancing trees, heap structures with their complexity proofs, and advanced variants that unlock better asymptotic bounds.

Binary Tree Traversals

A binary tree node holds a value and two child pointers. The three fundamental traversals visit nodes in different orders relative to the root:

  • Inorder (left, root, right): produces sorted output for a BST.
  • Preorder (root, left, right): useful for serialising a tree or copying it.
  • Postorder (left, right, root): useful for deleting a tree or evaluating expression trees.

Recursive inorder is a single function; the iterative version requires an explicit stack to simulate the call stack:

InorderIterative(root):
    stack = []
    curr = root
    while curr != null or stack not empty:
        while curr != null:
            stack.push(curr)
            curr = curr.left
        curr = stack.pop()
        visit(curr)
        curr = curr.right

The iterative form runs in $O(n)$ time and $O(h)$ space (where $h$ is tree height) - the same as the recursive version, but without the risk of stack overflow on deep trees.

BST Operations

A BST with $n$ nodes supports search, insert, and delete in $O(h)$ time, where $h$ is the height.

Search and Insert follow the BST property directly: go left if the key is smaller, right if larger, stopping when a match or null is found.

Delete has three cases:

  1. Leaf node: simply remove it.
  2. One child: splice the node out by linking its parent directly to its child.
  3. Two children: find the inorder successor (smallest key in the right subtree), copy its value to the current node, then delete the inorder successor (which has at most one right child).

Without balancing, sorted input produces a tree of height $h = n-1$, degrading all operations to $O(n)$.

AVL Trees: Enforcing Balance

An AVL tree maintains the height-balance invariant at every node:

$$|h(\text{left}) - h(\text{right})| \leq 1$$

Define the balance factor $\text{bf}(x) = h(x.\text{left}) - h(x.\text{right})$. After any insert or delete, walk back up the path to the root and fix any node where $|\text{bf}| = 2$ using one of four rotations:

Imbalance pattern Fix
Left-Left ($\text{bf}=2$, left child $\text{bf} \geq 0$) Right rotation at root
Right-Right ($\text{bf}=-2$, right child $\text{bf} \leq 0$) Left rotation at root
Left-Right ($\text{bf}=2$, left child $\text{bf} < 0$) Left rotation at left child, then right rotation at root
Right-Left ($\text{bf}=-2$, right child $\text{bf} > 0$) Right rotation at right child, then left rotation at root

The minimum number of nodes in an AVL tree of height $h$ satisfies $N(h) = N(h-1) + N(h-2) + 1$, which grows like the Fibonacci sequence: $N(h) \approx \phi^h / \sqrt{5}$. Inverting: $h \leq 1.44 \log_2(n+2) - 0.33$. AVL trees guarantee $O(\log n)$ operations.

Binary Heaps

A max-heap is a complete binary tree satisfying: every node’s key is $\geq$ both children’s keys. “Complete” means all levels are full except possibly the last, which is filled left to right.

Array Representation

A heap of size $n$ is stored in an array $A[1..n]$ (1-indexed). For a node at index $i$:

  • Parent: $\lfloor i/2 \rfloor$
  • Left child: $2i$
  • Right child: $2i+1$

No pointers needed. The completeness condition ensures all occupied indices form a contiguous range.

Heapify and Build-Heap

MaxHeapify restores the heap property at a node assuming both subtrees are already valid heaps:

MaxHeapify(A, i):
    largest = i
    if 2i <= heap_size and A[2i] > A[largest]: largest = 2i
    if 2i+1 <= heap_size and A[2i+1] > A[largest]: largest = 2i+1
    if largest != i:
        swap(A[i], A[largest])
        MaxHeapify(A, largest)

This runs in $O(\log n)$ by following one path from node $i$ to a leaf.

BuildHeap converts an arbitrary array into a heap:

BuildHeap(A):
    for i = floor(n/2) downto 1:
        MaxHeapify(A, i)

The naive bound is $O(n \log n)$, but the actual cost is $O(n)$. The proof uses the geometric series: a node at depth $d$ from the bottom requires at most $d$ swaps. Summing over all nodes:

$$\sum_{h=0}^{\lfloor \log n \rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil \cdot O(h) = O!\left(n \sum_{h=0}^{\infty} \frac{h}{2^h}\right) = O(n \cdot 2) = O(n)$$

since $\sum_{h=0}^{\infty} h x^h = x/(1-x)^2$ and at $x=1/2$ this equals $2$.

Priority Queue Operations

Operation Time
Insert $O(\log n)$ - insert at end, sift up
Extract-Max $O(\log n)$ - swap root with last, heapify down
Peek-Max $O(1)$
Decrease-Key $O(\log n)$ - sift up after reducing key
Build from array $O(n)$

$d$-ary Heaps

A $d$-ary heap gives each node $d$ children instead of 2. Extract-Min costs $O(d \log_d n)$ (must find the minimum of $d$ children per level). Decrease-Key costs $O(\log_d n)$ (fewer levels). For algorithms that perform many more decrease-key operations than extract-min (such as Dijkstra on dense graphs), $d=4$ is a common practical optimisation.

Fibonacci Heaps

Fibonacci heaps support the full priority queue interface with better amortised bounds:

Operation Amortised cost
Insert $O(1)$
Find-Min $O(1)$
Decrease-Key $O(1)$
Extract-Min $O(\log n)$
Merge $O(1)$

The key operation is Decrease-Key in $O(1)$ amortised. This is achieved by cutting the node from its parent immediately upon decrease (avoiding expensive reorganisation), and deferring consolidation until extract-min.

The practical consequence: Dijkstra’s algorithm with a binary heap runs in $O((V + E) \log V)$. With a Fibonacci heap it runs in $O(E + V \log V)$, which is better for dense graphs. The constant factors of Fibonacci heaps are high enough that binary heaps win in practice for most graph sizes.

The amortised analysis uses potential $\Phi = t + 2m$, where $t$ is the number of trees in the heap forest and $m$ is the number of marked nodes.

B-Trees for Disk Storage

A B-tree of order $t$ is a balanced search tree where:

  • Every non-root node has between $t-1$ and $2t-1$ keys.
  • All leaves are at the same depth.
  • Each internal node with $k$ keys has $k+1$ children.

The tree height is $h = O(\log_t n)$. By choosing $t$ to match the disk block size (so that one node fits in one block read), each operation touches $O(\log_t n)$ disk blocks. For $t = 500$ and $n = 10^9$, that is about $h \leq 4$ block reads per search - the reason every relational database uses a B-tree or B+-tree index.

Split operation: when a node is full ($2t-1$ keys), split it at the median key, pushing the median up to the parent. This keeps the tree balanced.

Examples

Example 1 - Build-Heap vs. repeated insert: Building a heap by inserting $n$ elements one by one costs $O(n \log n)$. BuildHeap costs $O(n)$ - a factor of $\log n$ faster. For $n = 10^6$, that is roughly $20\times$ fewer operations.

Example 2 - Dijkstra with different heaps: On a graph with $V = 10^5$ vertices and $E = 10^6$ edges:

  • Binary heap: $(E + V) \log V \approx 10^6 \times 17 \approx 1.7 \times 10^7$ operations.
  • Fibonacci heap: $E + V \log V \approx 10^6 + 10^5 \times 17 \approx 2.7 \times 10^6$ operations - roughly $6\times$ fewer, though with higher constants.

Example 3 - Iterative inorder for BST validation: To check that a BST is valid, run iterative inorder traversal and verify each visited value is strictly greater than the previous. This takes $O(n)$ time and $O(h)$ space, with no risk of recursion stack overflow on skewed trees.

Read Next: