Treap Data Structure: One Random Number Keeps Your Binary Tree Balanced

You have a binary search tree. You insert keys in sorted order. It degenerates into a linked list. Every operation becomes O(n). You know the fix: use a self-balancing tree. But AVL trees track heights and do double rotations. Red-black trees paint nodes and juggle five rebalancing cases. Both work. Both make you want to close the textbook.

This is what "entry-level interview question" looks like in some parallel universe.

The treap takes a lazier, smarter approach. Assign each node a random priority, then maintain heap order on those priorities. That single constraint, enforced by rotations, keeps the tree balanced in expectation. No height fields, no color bits, no case analysis. Just one random number per node, and the math of random binary search trees does the rest.

Cecilia Aragon and Raimund Seidel introduced the treap in 1989 at the IEEE Symposium on Foundations of Computer Science. The name is a portmanteau: tree + heap. Not the most creative naming, but at least it's honest. The core observation: a BST built by inserting keys in random order has expected height O(log n). You can't control insertion order in practice, but random priorities simulate it. The result is a tree whose shape is statistically identical to one built from a random permutation.

Same five keys. Left: inserted in order, became a sad linked list. Right: random priorities kept things balanced.

The Two Properties, Simultaneously

A treap is a rooted binary tree where each node stores a key and a randomly chosen priority. Two invariants hold at all times:

1. BST property on keys. For every node, all keys in its left subtree are smaller, and all keys in its right subtree are larger.
2. Heap property on priorities. For every node, its priority is smaller (min-heap) than the priorities of both its children.

Think of it like a company org chart where you're sorted alphabetically by name within each level, but your position in the hierarchy is determined entirely by how lucky you were in the priority lottery. The intern who rolled priority 1 ends up as CEO.

Given a set of nodes with distinct keys and distinct priorities, there exists exactly one treap satisfying both properties. The proof is inductive: the node with the smallest priority must be the root (heap property), it divides remaining nodes by key into left and right subsets (BST property), and the argument recurses on each subset.

The treap's shape depends only on the relative priority ordering, not on the sequence of insertions and deletions that built it.

Blue numbers are keys (BST order: left < parent < right). Yellow badges are priorities (heap order: parent < children). Both invariants hold simultaneously.

What Happens Inside

What each node stores

Each node stores four fields:

• key: the search key (ordered by BST property)
• priority: a random value (ordered by heap property)
• left: pointer to left child
• right: pointer to right child

Some implementations also store size (subtree count) to support order-statistic queries in O(log n).

Unlike array-backed structures, a treap is pointer-based. Nodes are heap-allocated and connected by left/right pointers. The tree's shape at any moment looks like a random BST, which means it is roughly balanced with high probability.

The shape is a random BST

A treap on n nodes with random priorities has the same distribution as a BST built by inserting n keys in uniformly random order. The node with smallest priority acts as if it were inserted first (it ends up at the root). The node with second-smallest priority acts as if inserted second. And so on. Since the priorities are random, the effective insertion order is a random permutation.

This is the sneaky genius of the treap. You can't control what order your users throw data at you. But you can fake it by assigning random priorities behind the scenes. Every known result about random BSTs applies to treaps directly.

Rotations restore heap order

When an insertion or deletion violates the heap property, rotations fix it. A right rotation at node u promotes u's left child to take u's place, pushing u down to the right. A left rotation does the mirror. Both preserve BST order while changing the parent-child relationship.

Right rotation: Y moves up, X moves down. Three pointer reassignments, O(1) work. BST order survives untouched.

Each rotation is O(1) work. It moves one node up and one node down while reassigning at most three pointers.

Two Approaches: Rotations vs Split/Merge

There are two ways to build a treap. The rotation-based approach inserts at the leaf and bubbles up. Split/merge instead decomposes the tree and reconstructs it. Both achieve the same complexity, but split/merge is more versatile because it naturally supports range operations and the implicit treap variant.

Split

Split(T, key) divides a treap T into two treaps: L (all keys <= key) and R (all keys > key).

The algorithm recurses down the tree. If the root's key is at most key, the root and its left subtree belong to L. We recursively split the right subtree and attach the left portion to the root's right. Otherwise, the root and its right subtree belong to R, and we recursively split the left subtree.

Each recursive call descends one level. Since expected height is O(log n), split runs in O(log n) expected time.

Split at key 4: keys {1, 3, 4} go left (green), keys {5, 6, 8, 10} go right (pink). One pass down the tree.

Merge

Merge(L, R) combines two treaps where all keys in L are less than all keys in R. It returns a single treap maintaining both properties.

The algorithm compares root priorities. The root with smaller priority (higher heap precedence) becomes the new root. We then recursively merge the other tree with the appropriate subtree of the winner. It's like a priority-based arm-wrestling match at every level.

Like split, each call descends one level. Merge runs in O(log n) expected time.

Merge: R's root (key 5, priority 2) beats L's root (key 3, priority 7). Winner becomes the new root. Colors show which pieces came from which treap.

Insert via split/merge

To insert a new node with key k:

1. Split the treap on k into L and R.
2. Merge L with the new node (a single-node treap).
3. Merge the result with R.

Two O(log n) operations. Total: O(log n). Beautifully simple.

Delete via split/merge

To delete key k:

1. Split on k-1 to get L and M (M contains k and everything larger).
2. Split M on k to get the node-to-delete and R.
3. Merge L and R.

Three splits/merges. Total: O(log n). The deleted node just falls out of the middle like a Jenga piece, except the tower doesn't collapse.

Insert via rotations (bubble up)

1. Insert the new node as a leaf using standard BST insertion.
2. While the node's priority is less than its parent's priority, rotate up.

The walk down costs O(depth). The rotations on the way up restore heap order. The expected number of rotations is at most 2, regardless of tree size.

The total rotations equal C + D, where C is the length of the right spine of the new node's left subtree, and D is the length of the left spine of its right subtree. Using indicator random variables and the fact that each rotation extends one of these spines by exactly one node, we get:

E[C + D] = 2 - 1/k - 1/(n-k+1)

where k is the rank of the inserted key. This is always less than 2. Expected rotations per insertion: fewer than 2. Two rotations. For a balanced tree. That's the entire price of admission.

Delete via rotations (trickle down)

1. Find the node to delete.
2. While it has children, rotate the child with smaller priority upward. This pushes the target node down.
3. Once it becomes a leaf, remove it.

This reverses the insertion process. Expected rotations: also O(1).

How Fast Is the Treap Data Structure?

The worst case O(n) occurs when all priorities happen to be sorted. With truly random priorities, the probability of this is roughly 1/n!, so you're more likely to win the lottery while being struck by lightning while finding a four-leaf clover. The expected height is 2 ln n + O(1), which is approximately 1.386 log₂ n + O(1).

Why search is O(log n)

The expected depth of node with rank r in a treap of n nodes is:

E[depth(r)] = H_r + H_{n-r+1} - O(1)

where H_k is the k-th harmonic number. This sums the probability that each other node is an ancestor. Node j is an ancestor of node i if and only if j has the highest priority (smallest value in min-heap) among all nodes with keys between i and j, inclusive. That probability is exactly 1/(|rank(j) - rank(i)| + 1).

Summing over all possible ancestors gives the harmonic series. The maximum depth (at the median rank) is 2H_{n/2} ≈ 2 ln(n/2) ≈ 1.386 log₂ n. This is the same bound as for random BSTs because a treap IS a random BST. That's the whole point.

Why split/merge are O(log n)

Both operations recurse once per level of the tree. Since expected height is O(log n), each call chain has expected length O(log n). The space for split/merge is O(log n) due to the recursion stack (or O(1) with iterative implementations).

Why build from sorted array is O(n)

If keys arrive sorted, you can build the treap bottom-up by maintaining a stack of the rightmost path. Each new key is appended to the right spine, then you walk up the stack popping nodes until you find one with smaller priority. This mirrors the "build Cartesian tree" algorithm and runs in amortized O(1) per insertion, O(n) total. Sorted data is the treap's worst nightmare for normal insertion, but its best friend for batch construction.

Why union is O(m log(n/m))

The treap union algorithm (Blelloch and Reid-Miller, 1998) splits the larger treap by the root of the smaller, recursively unions the resulting subtrees, then merges. The O(m log(n/m)) bound is information-theoretically optimal for merging two sorted sequences of sizes m and n. You literally cannot do better, and the treap just... does it.

The Implicit Treap: Arrays on Steroids

The implicit treap drops stored keys entirely. Instead, a node's "key" is its position in the in-order traversal, computed on the fly from subtree sizes. This turns the treap into a sequence data structure supporting:

• Insert at position i: O(log n)
• Delete at position i: O(log n)
• Range reverse: O(log n) with lazy propagation
• Range sum/min/max: O(log n) with augmentation
• Concatenate two sequences: O(log n)
• Split at position: O(log n)

The implicit treap is essentially a balanced rope. You'll see it in competitive programming whenever you need interval operations that arrays can't handle efficiently. It's the data structure equivalent of discovering your Swiss Army knife also has a flamethrower attachment.

One Structure, Every Language

Each treap implementation below uses the split/merge approach. Each provides insert, delete, search, split, and merge. Priorities use max-heap convention (higher priority = closer to root) to match the natural "bigger random number wins" intuition.

import random

class Node:
    __slots__ = ('key', 'priority', 'left', 'right', 'size')

    def __init__(self, key):
        self.key = key
        self.priority = random.randint(0, (1 << 62) - 1)
        self.left = None
        self.right = None
        self.size = 1

def get_size(node):
    return node.size if node else 0

def update(node):
    if node:
        node.size = 1 + get_size(node.left) + get_size(node.right)

def split(node, key):
    if not node:
        return None, None
    if node.key <= key:
        l, r = split(node.right, key)
        node.right = l
        update(node)
        return node, r
    else:
        l, r = split(node.left, key)
        node.left = r
        update(node)
        return l, node

def merge(left, right):
    if not left:
        return right
    if not right:
        return left
    if left.priority > right.priority:
        left.right = merge(left.right, right)
        update(left)
        return left
    else:
        right.left = merge(left, right.left)
        update(right)
        return right

def insert(root, key):
    l, r = split(root, key - 1)
    node = Node(key)
    return merge(merge(l, node), r)

def erase(root, key):
    l, r = split(root, key - 1)
    _, r = split(r, key)
    return merge(l, r)

def search(node, key):
    while node:
        if key == node.key:
            return True
        elif key < node.key:
            node = node.left
        else:
            node = node.right
    return False

What Problems Does It Solve?

The treap sits at a sweet spot: simpler to implement than AVL or red-black trees, yet just as powerful for the problems that matter.

Dynamic ordered sets. Any problem requiring insert, delete, and search on a sorted collection with O(log n) per operation. The treap handles this with less code than alternatives.

Order-statistic queries. With subtree sizes, you get k-th smallest element and rank queries in O(log n). Unlike hash maps, the treap maintains order.

Range splitting and merging. Need to cut a sorted set at a value and recombine pieces? Split and merge do this in O(log n). Red-black trees have no clean split operation. Good luck trying.

Interval manipulation (implicit treap). Insert at arbitrary positions, delete ranges, reverse subarrays, query range aggregates. All in O(log n). This solves the rope problem (efficient string concatenation/splitting) and covers operations that arrays do in O(n).

Set union, intersection, and difference. The treap union algorithm achieves O(m log(n/m)) for sets of sizes m and n, which is information-theoretically optimal. This matters for database query optimization and computational geometry.

Maintaining sorted data under adversarial input. Because balance depends only on random priorities (not insertion order), a treap cannot be forced into worst-case behavior by a malicious input sequence. AVL and red-black trees share this property, but treaps achieve it without deterministic rebalancing rules.

When Should You Reach for a Treap?

Look for these signals.

Signal 1: You need split or merge on an ordered set

If a problem asks you to partition a sorted collection at some value and later recombine the pieces, you are looking at a treap (or a closely related structure like a splay tree). Standard balanced BSTs don't expose efficient split.

Worked example: Dynamic median maintenance with splits

Problem: Maintain a set of integers. Support insert, delete, and "split at median" where you divide the set into lower and upper halves.

Why treap fits: Augment nodes with subtree sizes. Find the median rank (n/2). Split the treap at that key. You now have two treaps, each representing half the data. Recombine later with merge. Each operation is O(log n).

With a standard balanced BST, splitting requires extracting nodes one by one. With arrays, splitting is O(n). The treap's split/merge primitives make this natural.

Signal 2: You need to manipulate sequences by position

When the problem involves inserting elements at arbitrary positions, deleting ranges, reversing subarrays, or querying aggregates over arbitrary ranges of a sequence, the implicit treap is your tool.

Worked example: Rope with reverse

Problem: Given a string of n characters, support these operations efficiently:

• Insert character c at position i
• Delete character at position i
• Reverse the substring from position l to position r
• Print character at position i

Why treap fits: Use an implicit treap where each node holds a character. The "key" is the implicit position derived from subtree sizes. Insert at position i means split at i, merge the new character between the two halves. Reverse from l to r means split out the [l, r] segment, flip a lazy reversal flag on its root, merge it back. Each operation is O(log n).

An array handles access in O(1) but insertion and reversal in O(n). A linked list handles insertion in O(1) at a known position but finding that position takes O(n). The implicit treap gives O(log n) for everything. It's the Goldilocks data structure for sequence manipulation.

Signal 3: You need a balanced BST without the implementation complexity

If you are in a contest or time-pressured situation and need an ordered set with guaranteed balance, the treap (especially the split/merge variant) is shorter to implement correctly than AVL or red-black trees. The entire structure is defined by two symmetric functions (split and merge) plus one-line helpers.

Signal 4: Bulk set operations on sorted data

When you must compute union, intersection, or difference of two sorted sets, and n and m differ substantially in size, the treap union algorithm gives O(m log(n/m)), which is better than the O(m + n) merge-based approach when m is much smaller than n.

What to Remember

• A treap is a BST ordered by keys and a heap ordered by random priorities. One random number per node. That is the entire balancing mechanism.
• The shape matches a random BST: expected height 1.386 log₂ n.
• Insert and delete cost O(log n) expected time, with fewer than 2 expected rotations per operation.
• Split and merge are O(log n) and enable range operations, set algebra, and the implicit treap.
• The implicit treap variant is a sequence data structure supporting positional insert, delete, reverse, and range queries in O(log n).
• Treaps cannot be forced into worst-case behavior by adversarial insertion order.
• Simpler to implement than AVL or red-black trees while achieving the same expected bounds.

If you want to practice treap problems under realistic interview conditions, with voice-based interaction and rubric feedback on your communication, SpaceComplexity runs mock interviews covering advanced data structures. Explaining a split/merge approach out loud is harder than coding it silently. Worth a few reps before the real thing.

For more on balanced tree structures, see how AVL and red-black trees guarantee O(log n) deterministically, or revisit binary search tree fundamentals to see what the treap builds on. If order-statistic queries interest you, the heap data structure shares the priority-ordering idea in a simpler context.

Further reading

• Treap (Wikipedia)
• Treap implementation and implicit treap (CP-Algorithms)
• Open Data Structures: Treap
• CLRS Problem 13-4: Treaps (solutions)
• Jeff Erickson's lecture notes on Treaps and Skip Lists (UIUC)