Skip to content

What Is a Cartesian Tree

The Hidden Structure

In Chapters 1-3, the monotonic stack was a tool you used and threw away. But what if someone asked: what structure did the stack build while processing the array? The answer is a Cartesian Tree.

Every time you ran a monotonic stack over an array, you were implicitly constructing a binary tree. You just never looked at it. This chapter makes that tree explicit, because once you can see it, a whole class of problems becomes easy.

The Recursive Definition

Given an array A[l..r], the min-Cartesian Tree is built like this:

  1. Find the index m of the minimum element in A[l..r]. That's the root.
  2. The left subtree is the Cartesian Tree of A[l..m-1].
  3. The right subtree is the Cartesian Tree of A[m+1..r].
  4. If the range is empty, there's no node.

That's the whole definition. The minimum becomes the root, and everything splits around it.

You can also build a max-Cartesian Tree by using the maximum instead. The choice depends on the problem. We'll use min-Cartesian Trees by default.

Walkthrough: Building by Hand

Let's trace through A = [9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5].

Step 1: The global minimum is 1 at index 3. That's the root. The array splits into:

  • Left: [9, 3, 7] (indices 0-2)
  • Right: [8, 12, 10, 20, 15, 18, 5] (indices 4-10)

Step 2 (left subtree): The minimum of [9, 3, 7] is 3 at index 1. It becomes the root of the left subtree.

  • Left of 3: [9] (index 0) -- a leaf
  • Right of 3: [7] (index 2) -- a leaf

Step 3 (right subtree): The minimum of [8, 12, 10, 20, 15, 18, 5] is 5 at index 10. It becomes the root of the right subtree.

  • Left of 5: [8, 12, 10, 20, 15, 18] (indices 4-9)
  • Right of 5: empty

Step 4 (continuing right side): The minimum of [8, 12, 10, 20, 15, 18] is 8 at index 4.

  • Left of 8: empty
  • Right of 8: [12, 10, 20, 15, 18] (indices 5-9)

And so on. You keep splitting at the minimum until every element has its place.

The resulting tree looks like:

              1(3)
            /      \
         3(1)      5(10)
        /    \      /
      9(0)  7(2) 8(4)
                    \
                   10(6)
                  /    \
               12(5)  15(8)
                      /   \
                   20(7) 18(9)

(Notation: value(index))

Each node sits at the minimum of its subarray, and every split creates the left/right parts. It's a clean recursive decomposition.

Min-Cartesian tree for A=[9,3,7,1,8,12,10,20,15,18,5] — each node shows value and index

Why the Naive Construction Is Slow

If you follow the recursive definition directly, you need to find the minimum of a subarray at each step. Without preprocessing, that's O(N) per level, and the tree can have O(N) levels (when the array is sorted). That's O(N^2) worst case.

You could use a sparse table for O(1) range minimum queries, bringing it down to O(N log N) overall. But there's a better way.

O(N) Construction: The Right Spine Invariant

Here's the trick. Process elements left to right, and maintain the right spine of the Cartesian Tree built so far on a stack.

The right spine is the path from the root down to the rightmost node in the tree. In a min-Cartesian Tree, this path has increasing values (because each node is the minimum of its subarray, and as you go right, you're looking at subarrays that are further right and potentially have larger minimums).

So the stack holds an increasing sequence of values. Sound familiar? It's a monotonic stack.

Here's the algorithm:

  1. Start with an empty stack.
  2. For each element a[i], left to right:
  3. Pop all stack elements with value greater than a[i]. Keep track of the last one you popped.
  4. The last popped element becomes i's left child. (It was to the left of i in the array and was larger — it belongs in i's left subtree.)
  5. If the stack isn't empty, i becomes the right child of the current stack top. (The top is a smaller element to the left — i extends its right subtree.)
  6. Push i onto the stack.

Every element is pushed once and popped once. Total work: O(N).

Step-by-Step: [3, 2, 6, 1, 9]

Let's build the Cartesian Tree for A = [3, 2, 6, 1, 9].

i = 0, a[i] = 3: Stack is empty. Push 0. Stack: [0] (values: [3]) Tree: just node 3.

i = 1, a[i] = 2: Stack top is 0 (value 3). Since 3 > 2, pop it. Last popped = 0. Stack is now empty. Node 0 (value 3) becomes the left child of node 1 (value 2). Nothing left on the stack, so node 1 has no parent yet — it's the new root. Push 1. Stack: [1] (values: [2])

  2(1)
  /
3(0)

i = 2, a[i] = 6: Stack top is 1 (value 2). Since 2 < 6, don't pop. Node 2 becomes the right child of node 1. Push 2. Stack: [1, 2] (values: [2, 6])

  2(1)
  /  \
3(0) 6(2)

i = 3, a[i] = 1: Stack top is 2 (value 6). Since 6 > 1, pop it. Last popped = 2. Stack top is 1 (value 2). Since 2 > 1, pop it. Last popped = 1. Stack is empty. Node 1 (value 2) becomes the left child of node 3 (value 1). This brings the entire subtree rooted at 1 along with it. Node 3 is the new root. Push 3. Stack: [3] (values: [1])

        1(3)
        /
      2(1)
      /  \
   3(0) 6(2)

i = 4, a[i] = 9: Stack top is 3 (value 1). Since 1 < 9, don't pop. Node 4 becomes the right child of node 3. Push 4. Stack: [3, 4] (values: [1, 9])

        1(3)
       /    \
     2(1)   9(4)
     /  \
  3(0) 6(2)

Done. The root is node 3 (value 1), which is indeed the global minimum. The left subtree covers [3, 2, 6] and the right subtree covers [9].

Right-spine invariant construction — 5 panels showing how each element joins the tree

Why This Works

Think about what the stack represents at any point. It holds the right spine — the path from the root to the rightmost node. This path is increasing (for a min-Cartesian Tree), because each node on the right spine is the minimum of a successively smaller suffix of the array processed so far.

When a new element a[i] arrives:

  • If it's larger than the stack top, it just extends the right spine. It becomes the new rightmost node.
  • If it's smaller than some elements on the spine, those elements can't stay on the right spine anymore. They need to move into a[i]'s left subtree. The last one popped becomes a[i]'s left child, carrying its entire subtree along.

The "last popped" detail is important. You might pop several elements, but only the last one popped (the deepest one that was displaced) becomes the direct left child. All the others are already part of that element's subtree.

The Chapter 1 Connection

This is the same thing that happened in Chapter 1. Every push was extending the chain. Every pop was a chain disturbance — the new element broke the ordering and displaced something.

In Chapter 1, you tracked what happened during the push (extending) and pop (disturbing). Now you can see those operations were building a tree:

  • Push = new right child. The new element attaches to the right spine.
  • Pop = reparenting. The popped element moves from the right spine into the new element's left subtree.

The bitmask chaining from Chapter 1, the histogram boundaries from Chapter 3 — all of them were walking this tree without knowing it. The Cartesian Tree is the structure that unifies all the monotonic stack patterns you've learned.

Try It

The starter code reads an array and should output the parent of each node (or -1 for the root). Test it with:

5
3 2 6 1 9

Expected output: 1 3 1 -1 3

That means: node 0's parent is 1, node 1's parent is 3, node 2's parent is 1, node 3 is the root, node 4's parent is 3.

Try it on [9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5] and verify it matches the tree we built by hand earlier.