Skip to content
Tutorials Center
My learning

Topics

Lesson 104 of 225 ยท Trees

Cartesian Trees

Learn the Cartesian tree in Python: build it from an array in O(n) with a stack, see how it answers range minimum queries and why a treap is a Cartesian tree.

Most trees you have met are built from a sequence of insertions. A Cartesian tree is different: it is built from an array, and it records two things about that array at once. Reading the nodes in order from left to right gives back the array (the in-order traversal), and every node is smaller than all its descendants (the heap property). One tree, two orderings.

That sounds like a curiosity, but it is the structure behind range minimum queries, a famous linear-time construction, and the treap, a randomized balanced search tree. This lesson builds the tree with an O(n) stack algorithm, uses it to answer range queries, and shows the link to treaps.

Definition

Take an array a. Its (min-)Cartesian tree is defined recursively:

  • The root is the position of the smallest element. If there are ties, we pick the leftmost one.
  • The left subtree is the Cartesian tree of everything to the left of the root.
  • The right subtree is the Cartesian tree of everything to the right.

For a = [4, 2, 7, 1, 5, 3, 6] the minimum is 1 at index 3, so it is the root. The left part [4, 2, 7] has minimum 2 at index 1, and the right part [5, 3, 6] has minimum 3 at index 5:

flowchart TD
    r["1 (i=3)"] --> l["2 (i=1)"]
    r --> rr["3 (i=5)"]
    l --> l1["4 (i=0)"]
    l --> l2["7 (i=2)"]
    rr --> r1["5 (i=4)"]
    rr --> r2["6 (i=6)"]

The Cartesian tree of [4, 2, 7, 1, 5, 3, 6]. Each node shows its value and index. Reading indexes left to right gives 0 to 6 (in-order); each parent is smaller than its children (heap order).

The simple recursive build (scan for the minimum, recurse on both halves) costs O(nยฒ) in the worst case, for example on a sorted array. We can do much better.

Building in O(n) with a stack

Process the array from left to right and keep a stack of nodes along the right spine of the tree built so far (the path from the root going right). Their values are increasing from bottom to top.

For each new element x:

  1. Pop from the stack while the top is greater than x. The last node popped becomes the left child of the new node, since it and everything below it are larger and lie to the left.
  2. If the stack is not empty, the new node becomes the right child of the current top (which is smaller or equal).
  3. Push the new node.

The bottom of the stack at the end is the root. Each element is pushed once and popped at most once, so the total work is O(n) (the same amortized argument as the monotonic stack).

Because we pop only when the top is strictly greater, equal values stay on the stack and the later one becomes the right child of the earlier one. That makes the leftmost minimum the root, matching the definition.

Python Build a Cartesian tree with a stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output matches the picture: index 3 is the root, -1 means "no child".

Notice that sorted input is the easy case for this algorithm, not the hard one. An ascending array becomes a path leaning to the right (each element is the right child of the previous one), and the stack grows to size n without a single pop. The tree is tall, but we built it in O(n).

Range minimum queries

Here is the link to sparse tables and segment trees. In the Cartesian tree, the minimum of a[l..r] is the lowest common ancestor of nodes l and r.

Why? The root is the global minimum. If the range [l, r] lies entirely in the left part, the minimum of the range is somewhere in the left subtree, so ignore the root and look there. The same goes for the right part. The first time the root's index lies inside [l, r] (or the range straddles it), that root is the smallest value of the range, and it is exactly where the paths to l and r split.

So the query can be done by walking down from the root:

TEXT
node = root
while node is not inside [l, r]:
    node = left child if node > r else right child
return node

This costs O(height). In a worst-case tall tree that is O(n), but the structure converts RMQ into LCA: combine the tree with an Euler tour, a sparse table or binary lifting for LCA and you get O(1) or O(log n) queries. (The famous linear-preprocessing, constant-time RMQ algorithms are built exactly this way.)

Python Range minimum by walking down the tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Treaps: a Cartesian tree with random priorities

A binary search tree is only fast when it is balanced, and inserting keys in sorted order makes it a path. Here is a beautiful idea from red-black and other balanced trees: give every key a random priority and demand that the tree is a binary search tree by key and a min-heap by priority. That is exactly a Cartesian tree on the sequence of priorities when the keys are sorted.

A Cartesian tree is determined completely by the array. So a treap's shape depends only on the keys and their priorities, not on the insertion order. Since random priorities make the array of priorities random, the expected height is O(log n) whatever order the keys arrive in.

You can test this claim: build the tree once by inserting keys one at a time with rotations (the usual treap), and once by sorting the keys and running the stack algorithm on the priorities. The two trees are identical.

Python Treap insert equals the stack construction

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The node with priority 1 (key 30) is the root of the Cartesian tree, and it is also the root of the treap, because the heap property forces the smallest priority to the top.

When to use a Cartesian tree

  • Range minimum or maximum on a static array with a linear-time, low-memory structure.
  • Largest rectangle in a histogram and similar problems: the Cartesian tree gives, for every bar, the nearest smaller bar on each side, which is what the monotonic stack computes in the same pass.
  • Treaps and other randomized structures, where its definition explains why random priorities balance the tree.
  • Sorting. Building a Cartesian tree and then repeatedly extracting the root yields an adaptive sort that is fast on nearly sorted input.

Continue to the next lesson on heaps to see another structure that uses the min-at-the-top idea, but stored in a plain array instead of a tree of nodes.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which two properties does a min-Cartesian tree of an array satisfy?

    The in-order traversal reproduces the original index order, and the heap property puts the minimum at the root of each subtree.
  2. 2. What is the running time of the stack-based construction?

    Each element is pushed once and popped at most once, so the total number of stack operations is at most 2n.
  3. 3. In the stack algorithm, what becomes the left child of the new node?

    The popped nodes were larger than the new value and lie to its left, so the last popped (the highest in the chain) hangs as its left subtree.
  4. 4. The minimum of a[l..r] corresponds to which node of the Cartesian tree?

    The LCA of l and r is the first node on the way down whose index falls inside the range, and by the heap property it is the smallest value there.
  5. 5. Why is a treap's shape independent of insertion order?

    A binary search tree by key with heap order by priority is exactly one tree for a given set of distinct (key, priority) pairs.

Summary

  • A Cartesian tree is built from an array: the minimum is the root, and the left and right parts form the subtrees.
  • It is simultaneously in-order by index and heap-ordered by value.
  • A stack builds it in O(n): pop larger values to form the left child, attach the new node to the right of the top.
  • The minimum of a[l..r] is the LCA of l and r, which links range minimum queries to lowest common ancestors.
  • A treap is a Cartesian tree on random priorities, which is why its expected height is O(log n) for any insertion order.

Next: Heaps