Cartesian Tree

A Cartesian tree is a binary tree built from a sequence: every node is greater (or smaller, for a min-heap variant) than its descendants in heap order, while the in-order traversal recovers the original sequence. Used as the basis for treaps and for O(n) range-min queries.

Complexity

How it works

Build in O(n) using a stack: scan the sequence left to right; at each new element pop nodes from the stack while they are smaller (for max-heap), make the last popped node the new node's left child, attach the new node as the right child of the stack top, and push it. The treap variant assigns random priorities to balance like a randomized BST.

Python implementation

class Node:
    __slots__ = ("val", "left", "right")
    def __init__(self, val):
        self.val, self.left, self.right = val, None, None


def build_cartesian_tree(seq):
    """Build a max-heap-ordered Cartesian tree from a sequence in O(n)."""
    stack = []
    for v in seq:
        n = Node(v)
        last = None
        while stack and stack[-1].val < v:
            last = stack.pop()
        if last:
            n.left = last
        if stack:
            stack[-1].right = n
        stack.append(n)
    return stack[0] if stack else None


def in_order(root, out):
    if not root: return
    in_order(root.left, out); out.append(root.val); in_order(root.right, out)


root = build_cartesian_tree([3, 2, 6, 1, 9, 4, 5])
out = []; in_order(root, out)
print(out)   # [3, 2, 6, 1, 9, 4, 5]  (in-order recovers the input)


# Treap = Cartesian tree on random priorities — gives expected O(log n).
import random

class TreapNode:
    __slots__ = ("key", "prio", "left", "right")
    def __init__(self, key):
        self.key = key
        self.prio = random.random()
        self.left = self.right = None

Trade-offs

• Built in O(n) from a sequence — useful for range-min/max query preprocessing.
• Treap variant gives expected O(log n) for ordered set operations with simpler code than red-black trees.
• Worst case O(n) on adversarial input without randomization.
• Mostly an academic / competitive-programming structure; production systems use balanced BSTs or skip lists.

← Back to Algorithms

5. Construction Step by Step

The linear-time construction keeps a stack holding the right spine of the tree built so far, from the root down to the most recent node. For each new element, nodes on the stack that are larger than it are popped; the last popped node becomes the new element's left child, because those elements come before it in the sequence and are larger. If the stack is not empty after popping, the new element becomes the right child of the top of the stack. Finally the new element is pushed. Because each element is pushed and popped at most once, construction is O(n) even though an individual step can pop many nodes.

6. Structure and Properties

Two invariants define the tree. Heap order: every node is smaller than its descendants in the min variant, so the root is the minimum of the whole sequence and the root of any subtree is the minimum of a contiguous range. Symmetric order: an in-order traversal returns the original sequence, so each subtree corresponds to a contiguous subarray. Together they give the key fact used for range-minimum queries: the minimum of a[i..j] is the lowest common ancestor of nodes i and j. With distinct values the tree is unique for a given sequence.

The shape of the tree reflects the input. A random permutation gives expected depth O(log n), the same analysis that makes randomized quicksort and treaps efficient; in fact, building a Cartesian tree by recursion, choosing the minimum as root and recursing on each side, performs exactly the comparisons quicksort would perform with the minimum as pivot. A sorted sequence gives a path, since each new element is larger than all before it and becomes a right child. This sensitivity to order is harmless for range-minimum queries, which use the tree only through LCA structures that do not depend on depth, but it matters for anything that walks the tree directly.

7. Worked Example: Range Minimum via LCA

def cartesian_parents(a):
    """Return parent index of each position (root has -1), min-heap order."""
    n, stack = len(a), []
    parent = [-1] * n
    for i in range(n):
        last = -1
        while stack and a[stack[-1]] > a[i]:
            last = stack.pop()
        if last != -1:
            parent[last] = i
        if stack:
            parent[i] = stack[-1]
        stack.append(i)
    return parent

def range_min(a, parent, i, j):
    """Naive LCA by walking up; O(depth). Production code uses Euler tour + sparse table."""
    anc = set()
    x = i
    while x != -1:
        anc.add(x); x = parent[x]
    y = j
    while y not in anc:
        y = parent[y]
    return a[y]

a = [3, 1, 4, 2, 5, 0, 6]
par = cartesian_parents(a)
print(par)                        # [1, 5, 3, 1, 3, -1, 5]
print(range_min(a, par, 2, 4))    # 2
print(range_min(a, par, 0, 6))    # 0

Pairing the Cartesian tree with an Euler tour and a sparse table over depths gives O(n) preprocessing and O(1) range-minimum queries, which is the classical route to optimal RMQ.

8. Where Cartesian Trees Are Used

A treap is a Cartesian tree over (key, priority) pairs. Because priorities are random, the expected depth is O(log n), so insert, delete, and search run in expected O(log n) with simpler code than red-black or AVL trees.

9. Pitfalls

• With duplicate values, decide whether to pop on > or >=; the choice changes the tree shape and which equal element is reported.
• Sorted input produces a path of depth n; recursive traversals will hit Python's recursion limit, so traverse iteratively.
• The tree is static: inserting into the middle of the sequence is not supported, unlike a treap keyed by value.

10. Related Topics

• Binary Search Tree, Splay Tree
• AVL Tree, Red-Black Tree

Featured Videos