Cartesian Tree, in depth: linear-time construction, range minimum via LCA, ties, treaps and when to use one

Definition

Given an array A[0..n-1], the min-Cartesian tree is defined recursively. The root is the position of the minimum element. Its left subtree is the Cartesian tree of the elements to the left of that position, and its right subtree is the Cartesian tree of the elements to its right. An empty range gives an empty tree.

Two properties follow directly. The tree is heap-ordered by value: every node is no larger than its descendants, because each node was the minimum of the range that contains all of them. And it is a binary search tree by index: an in-order traversal visits positions 0, 1, ..., n-1 in order, because everything to the left of a node's position went into its left subtree. With distinct values the tree is unique, since each recursive step has exactly one choice. A max-Cartesian tree swaps minimum for maximum and is used the same way for range maximum.

Cartesian trees were introduced by Jean Vuillemin in 1980. The name comes from plotting each element as a point (index, value) in the plane: the tree is the unique tree that is a search tree in x and a heap in y.

Building it in O(n) with a stack

The recursive definition suggests an O(n log n) or worst-case O(n squared) algorithm: find the minimum, split, recurse. A better approach processes the array left to right while maintaining the tree for the prefix seen so far. The key observation is that a new element can only attach to the right spine of the current tree, the path from the root going right, because it is the rightmost element in the in-order sequence.

Keep the right spine on a stack, root at the bottom. For each new element x at position i, pop every spine node whose value is greater than x. Those nodes, being larger, must sit below x, and since they precede it in index order, the last node popped becomes x's left child. If the stack is not empty after popping, x becomes the right child of the new top. Then push x.

def build_cartesian_tree(a):
    """Min-Cartesian tree. Returns (root, parent, left, right) as index arrays; -1 means none."""
    n = len(a)
    parent, left, right = [-1] * n, [-1] * n, [-1] * n
    stack = []                       # right spine, root at stack[0]
    for i, x in enumerate(a):
        last = -1
        while stack and a[stack[-1]] > x:   # strict: equal values stay above (see ties)
            last = stack.pop()
        if last != -1:
            left[i] = last
            parent[last] = i
        if stack:
            right[stack[-1]] = i
            parent[i] = stack[-1]
        stack.append(i)
    root = stack[0] if stack else -1
    return root, parent, left, right

The running time is linear by an amortised argument: each index is pushed once and popped at most once, so the total work in all the inner loops is at most n pops. Memory is three integer arrays plus a stack of at most n entries.

Tracing the worked example

Run it on A = [5, 3, 8, 2, 6, 4, 7]. The stack holds indices; values are shown in brackets.

The root is the bottom of the stack, index 3 with value 2. Notice step 5: index 4 was briefly the right child of 3, then 4 (value 4) arrived, pushed index 4 down into its own left subtree, and took its place. That overwrite is correct: the right-child link of the stack top always points at the newest spine node. Likewise, when index 3 pops indices 2 and 1, index 2 stays attached under index 1, so the whole subtree moves under 3 with one link.

Ties

With repeated values the tree is no longer unique, and the comparison in the pop loop decides which shape you get. Popping only while the top is strictly greater means an earlier equal element stays on the stack and becomes an ancestor of the later one. The result is that the root of any subtree is the leftmost minimum of its range, and range queries return the leftmost minimum position.

Take A = [2, 1, 3, 1]. With strict popping, index 1 becomes the root. When index 3 arrives it pops index 2 (3 > 1) and stops at index 1, because 1 is not greater than 1, so index 3 becomes the right child of index 1 and index 2 becomes its left child. A query over the whole array returns index 1, the leftmost minimum. Changing the comparison to >= makes the later equal element the ancestor and queries return the rightmost minimum. Pick one deliberately; tests that only use distinct values will not notice the difference, and downstream code that needs a stable position will.

Why range minimum is lowest common ancestor

Claim: for i ≤ j, the minimum of A[i..j] is at the lowest common ancestor of nodes i and j in the Cartesian tree.

Proof sketch. Let v be the LCA. Every node's subtree covers a contiguous index range, so v's subtree covers a range containing both i and j, and therefore all of i..j. Because v is the lowest common ancestor, i and j are not both in one child subtree: either one of them is v, or i lies in v's left subtree and j in its right, which puts v's position between them. Either way v's position is inside [i, j]. Finally v is the minimum of its whole subtree by heap order, and [i, j] lies inside that subtree, so v's value is the minimum of A[i..j].

Check it on the example: RMQ(0, 2) asks about 5, 3, 8; the LCA of nodes 0 and 2 is node 1, value 3. RMQ(2, 4) asks about 8, 2, 6; the LCA of nodes 2 and 4 is the root, value 2. RMQ(4, 6) asks about 6, 4, 7; the LCA is node 5, value 4. All correct.

The reduction also runs the other way: LCA in any tree reduces to RMQ over its Euler tour depths. Combining the two directions is how Bender and Farach-Colton showed that RMQ on any array can be answered in O(1) after O(n) preprocessing.

Answering queries: Euler tour plus sparse table

To answer LCA quickly, walk the tree depth-first and record every node each time you visit it, together with its depth. That Euler tour has 2n - 1 entries. The LCA of u and v is the shallowest node in the tour between the first occurrences of u and v. A sparse table over the tour depths answers that minimum in O(1) by covering the range with two overlapping power-of-two blocks.

def euler_tour(root, left, right):
    tour, depth, first = [], [], {}
    stack = [(root, 0, 0)]                      # (node, depth, state); iterative: depth can be n
    while stack:
        node, d, state = stack.pop()
        if state == 0:
            first.setdefault(node, len(tour))
        tour.append(node); depth.append(d)
        kids = [k for k in (left[node], right[node]) if k != -1]
        if state < len(kids):
            stack.append((node, d, state + 1))  # come back to node after this child
            stack.append((kids[state], d + 1, 0))
    return tour, depth, first


class CartesianRMQ:
    def __init__(self, a):
        self.a = a
        root, _, left, right = build_cartesian_tree(a)
        self.tour, depth, self.first = euler_tour(root, left, right)
        m = len(self.tour)
        self.log = [0] * (m + 1)
        for k in range(2, m + 1):
            self.log[k] = self.log[k // 2] + 1
        self.sp = [list(range(m))]              # sp[k][i]: tour index of min depth in [i, i + 2^k)
        k = 1
        while (1 << k) <= m:
            prev, half = self.sp[-1], 1 << (k - 1)
            row = []
            for i in range(m - (1 << k) + 1):
                x, y = prev[i], prev[i + half]
                row.append(x if depth[x] <= depth[y] else y)
            self.sp.append(row)
            k += 1
        self.depth = depth

    def argmin(self, i, j):
        """Index of the minimum of a[i..j], inclusive, i <= j."""
        l, r = sorted((self.first[i], self.first[j]))
        k = self.log[r - l + 1]
        x, y = self.sp[k][l], self.sp[k][r - (1 << k) + 1]
        return self.tour[x if self.depth[x] <= self.depth[y] else y]


rmq = CartesianRMQ([5, 3, 8, 2, 6, 4, 7])
assert [rmq.argmin(0, 2), rmq.argmin(2, 4), rmq.argmin(4, 6)] == [1, 3, 5]

Complexity, stated precisely: building the tree is O(n), the Euler tour O(n), the sparse table O(n log n) time and memory, and each query O(1). To reach O(n) preprocessing, split the Euler tour depth sequence into blocks of size about (log n)/2. Adjacent depths differ by exactly one, so there are only about the square root of n distinct block shapes; precompute answers for each shape, build a sparse table over block minima only, and combine. That is the ±1 RMQ technique. It is elegant and rarely worth implementing: the constant factors usually lose to a plain sparse table built directly on the array.

Treaps: the same tree with random priorities

A treap stores keys with random priorities and is simultaneously a binary search tree on keys and a heap on priorities. That is exactly a Cartesian tree of the (key, priority) points. Because the priorities are random, the expected depth is O(log n) no matter what order keys arrive in, which is why treaps make simple balanced search trees. Insertion places a key as in an ordinary BST and rotates it up while its priority violates heap order; deletion rotates it down to a leaf. If you know heap operations and BST traversal, a treap is the two combined.

The contrast with an array Cartesian tree is important: the array tree uses the data itself as priorities, so its shape is whatever the data dictates. A sorted array gives a tree that is a single path of depth n.

Other uses of the same structure

• Nearest smaller values. The stack construction computes, for every element, its previous smaller element as a by-product. For distinct values, a node's parent is whichever of its previous-smaller and next-smaller neighbours has the larger value.
• Contribution counting. Element i is the minimum of exactly (size of left subtree + 1) times (size of right subtree + 1) subarrays. Summing value times that count gives the sum of minimums over all subarrays in O(n).
• Largest rectangle in a histogram. Each bar's maximal rectangle spans its Cartesian subtree's index range, so the best rectangle is the maximum over nodes of value times subtree width.
• Adaptive sorting. Levcopoulos and Petersson's sort builds a Cartesian tree and extracts minima with a priority queue; it runs faster on inputs that are already nearly sorted.

Choosing a range-minimum structure

A Fenwick tree is the usual answer for prefix sums but does not support arbitrary range minimum, because minimum has no inverse; reach for a segment tree instead.

Failure modes

• Recursion depth. Sorted or nearly sorted input produces a path-shaped tree of depth n. Recursive construction or traversal overflows the stack in most languages long before memory runs out; keep both iterative, as above.
• Unspecified ties. Strict versus non-strict comparison changes which position is returned. Document the rule and test with duplicates.
• Inclusive versus exclusive ranges. The code above uses inclusive [i, j]. Mixing conventions gives answers off by one element that pass most random tests.
• Memory blow-up. The sparse table over the Euler tour has about (2n) log(2n) entries, roughly twice a sparse table on the array itself. For large arrays that difference matters.
• Mutation. The structure is static. Changing one value can change the tree's shape globally; rebuild, or use a segment tree.

What to do next

1. Run the code above and add a brute-force checker comparing argmin(i, j) with min over the slice for random arrays that include duplicates.
2. Trace the stack construction on [2, 1, 3, 1] by hand and confirm the tie rule you expect.
3. Use the parent array to compute the sum of subarray minimums and verify it against brute force on small inputs.
4. Implement a treap with rotations and compare its depth on sorted input with a plain BST.
5. Benchmark a sparse table on the array against the Cartesian tree version for your data size before choosing.