Leftist Tree

Leftist tree (or leftist heap) is a pointer-based mergeable priority queue data structure within computation and algorithms implemented as a heap-ordered binary tree that is intentionally unbalanced toward the left so that its rightmost path remains logarithmically short. Invented by Clark Allan Crane in his 1972 Stanford University doctoral dissertation on linear lists and priority queues and popularized by Donald Ervin Knuth in Volume 3 (Sorting and Searching, 1973) of The Art of Computer Programming, the leftist tree was the first priority queue to support merging (Meld) of two disjoint heaps of total size n in O(log n) worst-case time, compared with the Θ(n) time required to merge two array-based binary heaps.

Rather than trying to keep the entire binary tree height-balanced like an AVL or red-black search tree, a leftist tree enforces a local structural inequality at every internal node x: the null-path length (or s-value / rank) s(left(x)) of its left child is at least as large as the null-path length s(right(x)) of its right child. Because every step down the right spine decreases s(x) by at least 1 and a subtree with null-path length k contains at least 2^k − 1 internal nodes, the rightmost path from the root to an external null link has length at most ⌊log₂(n + 1)⌋. Consequently, all priority queue updates—Meld, Insert, and Delete-Min—can perform their work entirely along the short right spines of the participating trees and restore the leftist invariant on the way back up via simple left-right child swaps, laying the foundation for later self-adjusting and amortized mergeable heaps including the skew heap, pairing heap, Fibonacci heap, and Brodal queue.

Definition of s(x) (Distance to the Nearest External Node)

In an extended binary tree where every missing child pointer is represented as an explicit external node (null link □), the null-path length (denoted s(x) by Knuth, for shortest path) of any node x is defined as the length (number of edges) of a shortest path from x downward to an external node:

• For any external null node □, s(□) = 0.
• For any internal node x with children left(x) and right(x):

A binary tree is a height-biased leftist tree (HBLT) if, at every internal node x, the null-path length of the left child is greater than or equal to the null-path length of the right child:

Combining this inequality with the recurrence for s(x) yields two immediate simplifications at every node x of a leftist tree:

1. s(x) = 1 + s(right(x)), meaning the shortest path from x to an external node always follows the rightmost spine of the subtree rooted at x.
2. While the left subtree of x may be arbitrarily deep (even forming a degenerate linear chain of length Θ(n)), the right spine is guaranteed to be compact.

Logarithmic Bound on Right-Spine Length

Theorem (Crane, 1972; Knuth, 1973): If the subtree rooted at x in a leftist tree has null-path length s(x) = k, then that subtree contains at least 2^k − 1 internal nodes. Equivalently, in an n-node leftist tree, the length of the rightmost path from the root to an external node satisfies:

Proof: Because s(root) = k is the minimum distance from the root to any external node, every external node lies at depth at least k. Therefore, Levels 0, 1, …, k − 1 of the binary tree are completely filled with internal nodes, totaling 2⁰ + 2¹ + … + 2^k−1 = 2^k − 1 internal nodes. Since the tree has n internal nodes in total, n ≥ 2^k − 1, so k ≤ log₂(n + 1), and because k is an integer, k ≤ ⌊log₂(n + 1)⌋.

In a leftist heap, every node x simultaneously obeys the min-heap order property (key[x] ≤ key[left(x)] and key[x] ≤ key[right(x)]) and the leftist property (s(left(x)) ≥ s(right(x))).

Recursive and Iterative Right-Spine Meld

The central primitive of a leftist heap is Meld(H₁, H₂), which merges two node-disjoint leftist heaps of sizes n₁ and n₂ (with n = n₁ + n₂) into a single valid leftist heap in O(log n) worst-case time:

1. Base case: If H₁ = □, return H₂; if H₂ = □, return H₁.
2. Root comparison: Compare key[H₁] and key[H₂]. Without loss of generality, assume key[H₁] ≤ key[H₂] (otherwise swap the roles of H₁ and H₂). The root of H₁ becomes the root of the merged heap, and its entire left subtree left(H₁) is left untouched.
3. Recursive right-spine merge: Set right(H₁) ← Meld(right(H₁), H₂).
4. Leftist restoration: Compare s(left(H₁)) and s(right(H₁)). If s(left(H₁)) < s(right(H₁)), swap the two child pointers left(H₁) ↔ right(H₁).
5. Rank update: Update s(H₁) ← 1 + s(right(H₁)) and return H₁.

Because each recursive step advances down the right spine of either H₁ or H₂, the total number of comparisons and pointer updates is at most:

All other priority queue operations reduce directly to Meld:

• Find-Min(H): Return key[H] in O(1) worst-case time.
• Insert(H, x): Create a 1-node leftist tree with s(x) = 1 and call Meld(H, x) in O(log n) worst-case time.
• Delete-Min(H): Remove the root of H and return Meld(left(H), right(H)) in O(log n) worst-case time.
• Decrease-Key(H, x, k) (with parent pointers): Cut the subtree rooted at x from its parent p(x), walk upward from p(x) recomputing s(u) and swapping children as needed until an ancestor's s-value stops changing (at most O(log n) steps because each step moves up along a right child whose s-value was smaller), update key[x] ← k, and Meld(H, x) in O(log n) worst-case time.

O(n) Bottom-Up Heap Construction via FIFO Queue

Inserting n elements one by one into an initially empty leftist heap takes O(n log n) time. Knuth (1973) showed how to initialize an n-node leftist heap in O(n) worst-case time using a first-in, first-out (FIFO) queue Q:

1. Place all n elements into Q as n individual 1-node leftist trees.
2. While Q contains two or more trees, dequeue the first two trees T₁ and T₂ from the front of Q, compute T ← Meld(T₁, T₂), and enqueue T at the back of Q.
3. Return the single remaining tree in Q.

In pass j ≥ 1, the algorithm pairs up ⌈n / 2^j⌉ trees of size 2^j−1, each meld taking at most O(j) time. Summing over all passes gives ∑_{j=1..⌈log n⌉} (n / 2^j) · O(j) = O(n).

Weight-Biased Leftist Trees (Cho and Sahni, 1998)

Seonghun Cho and Sartaj Sahni (1998) introduced the weight-biased leftist tree (WBLT), which replaces the null-path length s(x) with the subtree weight w(x) (the total number of internal nodes in the subtree rooted at x, plus 1) and enforces w(left(x)) ≥ w(right(x)) at every node. Because the sum of weights of two merged trees w(H₁) + w(H₂) is known before recursing into the right child, a WBLT can decide whether to swap left and right children on the way down the right spine in a single top-down pass without needing a bottom-up return pass or stack frame unwind.

Purely Functional Persistence and Eppstein's k-Shortest Paths

Because Meld(H₁, H₂) in a leftist tree modifies only the O(log n) nodes along the right spines of H₁ and H₂ and never touches their left subtrees, allocating fresh copies of the O(log n) right-spine nodes during each Meld yields a fully persistent (purely functional) mergeable priority queue in O(log n) worst-case time and space per operation (unlike the skew heap or splay tree, whose amortized bounds break under persistence if an adversary repeatedly queries an expensive historical version).

This persistent O(log n) Meld is a foundational building block in David Eppstein's 1998 algorithm for finding the k shortest paths between two vertices in a directed graph in O(E + V log V + k) time: after computing a shortest-path tree via Dijkstra's algorithm, each vertex v shares a persistent leftist heap of sidetrack edges with its shortest-path parent by persistently inserting v's own outgoing non-tree edges into the parent's leftist heap in O(outdeg(v) + log E) time and space.

How many bits per node are needed to store the null-path length s(x)?

Because s(x) ≤ ⌊log₂(n + 1)⌋, even a leftist tree containing n = 2⁶⁴ − 1 nodes (spanning the entire 64-bit address space) has s(x) ≤ 64. Thus a single 6-bit or 8-bit unsigned integer field (uint8) inside each node suffices to store s(x) for any physically realizable tree.

Why is an arbitrary deletion or Decrease-Key harder in a leftist tree than in a binary heap?

In a standard binary heap, every path from a node to the root has length at most ⌊log₂ n⌋, so bubbling a decreased key up through its ancestors takes O(log n) time. In a leftist tree, only the rightmost spine is guaranteed to have length O(log n); a path that follows left child links can have length Θ(n). Therefore, Decrease-Key cannot simply bubble a key up to the root by swapping values; instead, it must sever the subtree at x, update s-values up to the first ancestor where s remains unchanged (which traverses at most O(log n) right links), and Meld the severed subtree back into the root.

How does a leftist tree compare to a skew heap in practice?

A skew heap omits the s(x) field and swaps the left and right children of every node visited along the right spine during Meld. While a skew heap saves 1 byte of storage per node and avoids comparing s-values, a leftist tree performs child swaps only when s(left(x)) < s(right(x)), guarantees worst-case rather than merely amortized O(log n) time, and supports worst-case persistent path copying without degradation under repeated branching queries.

1. Crane, C. A. (1972). Linear Lists and Priority Queues as Balanced Binary Trees. Technical Report STAN-CS-72-259 (Ph.D. dissertation), Computer Science Department, Stanford University. https://i.stanford.edu/pub/cstr/reports/cs/tr/72/259/CS-TR-72-259.pdf
2. Knuth, D. E. (1973). The Art of Computer Programming, Volume 3: Sorting and Searching (Section 5.2.3, pp. 150–152). Reading, MA: Addison-Wesley. https://www-cs-faculty.stanford.edu/~knuth/taocp.html
3. Cho, S., & Sahni, S. (1998). "Weight biased leftist trees and modified skip lists." ACM Journal of Experimental Algorithmics, 3, Article 2. https://doi.org/10.1145/297096.297111
4. Eppstein, D. (1998). "Finding the k shortest paths." SIAM Journal on Computing, 28(2), 652–673. https://doi.org/10.1137/S0097539795290477
5. Tarjan, R. E. (1983). Data Structures and Network Algorithms (Chapter 3: Heaps, pp. 33–43). Philadelphia, PA: SIAM. https://doi.org/10.1137/1.9781611970265