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