Cartesian Trees: One Array, Two Structural Properties, and Linear-Time Construction

A Cartesian tree turns a one-dimensional array into a binary tree with two simultaneous guarantees:

1. An in-order traversal of the tree reproduces the original array order.
2. Every parent has a smaller value than its children, so the tree satisfies the min-heap property.

These requirements are simple individually, but their combination is powerful. The array determines the left-to-right order, while the values determine which elements rise toward the root. This gives the array a tree-shaped interpretation without losing its original ordering.

This article develops the idea using the array [3, 2, 5, 1, 4]. We will construct its Cartesian tree directly from the definition, examine why that approach can require $O(n^2)$ time, and then derive a monotonic-stack construction that runs in one $O(n)$ pass. We will also see why a range minimum is the lowest common ancestor of the range endpoints and how a Treap fits the same general pattern.

The two defining invariants​

Let the input array be:

[3, 2, 5, 1, 4]

A min Cartesian tree for this array must satisfy two invariants.

In-order order preservation​

An in-order traversal visits the left subtree, then the node itself, then the right subtree. For a Cartesian tree, that traversal must reproduce the array exactly:

3, 2, 5, 1, 4

This means that the tree cannot rearrange the array's left-to-right order. A node representing the value 5 must appear after the nodes representing 3 and 2, but before the nodes representing 1 and 4 in the traversal.

Positions therefore matter as much as values. Each tree node represents an array element at a particular index. Nodes in its left subtree correspond to earlier array positions, and nodes in its right subtree correspond to later positions.

Min-heap order​

The value at every parent must be smaller than the value at each child. Values increase as we move downward from the root. This is the min-heap condition.

The root of the entire tree must therefore contain the global minimum of the array. In this example, the minimum is 1, so 1 must be the root.

The same principle applies recursively. The root of any subtree contains the smallest value in the contiguous array interval represented by that subtree.

These two rules control different aspects of the structure:

• In-order order controls horizontal, left-to-right placement.
• Heap order controls vertical, ancestor-to-descendant placement.

The Cartesian tree is the structure that satisfies both at once.

Constructing the tree directly from the definition​

The definition suggests a natural recursive algorithm:

1. Find the minimum value in the current array interval.
2. Make that minimum the root of the current subtree.
3. Recursively construct the left subtree from the elements before the minimum.
4. Recursively construct the right subtree from the elements after the minimum.

For [3, 2, 5, 1, 4], the minimum is 1, at index 3. Thus, 1 becomes the root. The elements before it form the left interval:

[3, 2, 5]

The elements after it form the right interval:

[4]

The right subtree is immediate: 4 becomes the right child of 1.

Now construct the left subtree from [3, 2, 5]. Its minimum is 2, so 2 becomes the left child of 1. The elements before 2 form [3], and the elements after 2 form [5]. Consequently, 3 becomes the left child of 2, and 5 becomes the right child of 2.

The final parent-child relationships are:

1 is the root
1.left  = 2
1.right = 4
2.left  = 3
2.right = 5

A corresponding diagram is:

      1
     / \
    2   4
   / \
  3   5

The in-order traversal is:

3, 2, 5, 1, 4

The heap comparisons are:

1 < 2
1 < 4
2 < 3
2 < 5

Both invariants hold.

Every subtree represents a contiguous interval​

One useful way to reason about a Cartesian tree is to associate each subtree with a contiguous interval of the original array.

For the example:

• The whole tree represents [3, 2, 5, 1, 4].
• The subtree rooted at 2 represents [3, 2, 5].
• The leaf rooted at 3 represents [3].
• The leaf rooted at 5 represents [5].
• The leaf rooted at 4 represents [4].

The root of each subtree is the minimum value in that interval. The position of that minimum divides the interval into the left and right subintervals.

For the root 1, the division is:

[3, 2, 5] [1] [4]

For the node 2, the division inside its interval is:

[3] [2] [5]

This interval perspective explains why the structure is useful for range minimum queries. It also makes the recursive definition almost unavoidable: the minimum has to be the root, and the values on either side have to form its two subtrees.

Why direct construction can take quadratic time​

The recursive definition is clear, but finding the minimum of every interval can repeat a large amount of work. If the current interval contains $k$ elements, scanning it to find its minimum costs $O(k)$ time.

For a favorable input, the minimum may split the interval into reasonably sized pieces. However, the worst case occurs when the minimum repeatedly appears at one end of the current interval. Then one recursive call has size only one smaller than its parent, producing scans of sizes $n$, $n-1$, $n-2$, and so on.

The total work can be proportional to:

The tree is still correct. The problem is repeated searching. Elements that were considered while finding one interval minimum may be scanned again while finding the minimum of a related interval.

The direct method therefore has worst-case time complexity $O(n)$ for each recursive level in the most unbalanced case, giving total worst-case time $O(n^2)$. Its recursion depth can also reach $O(n)$ when the resulting tree is a chain.

The goal is to construct the same tree while processing each array element only a small number of times.

The key observation: maintain the right spine​

The linear-time construction uses a monotonic stack. The stack represents the right spine of the Cartesian tree built from the prefix processed so far.

A tree's right spine is the path obtained by starting at the subtree root and repeatedly following the right child. When a new array element is processed from left to right, it is appended at the right edge of the processed prefix. Any structural change caused by that new element must therefore occur near the existing right boundary.

Nodes that are not on the right spine are already positioned correctly relative to the elements processed so far. They do not need to be reconsidered. The stack stores the candidate ancestors that the new value might need to displace.

For a min Cartesian tree with distinct values, the right-spine values are maintained in increasing order as we move from the root toward the rightmost node. When a new value $x$ arrives:

1. Pop nodes from the stack while their values are larger than $x$.
2. The last node popped becomes the left child of $x$.
3. If a node remains on the stack, make $x$ its right child.
4. Push $x$ onto the stack.

The important detail is that popping does not delete a node from the tree. It only removes that node from the current right spine. The popped nodes remain connected as part of the new node's left subtree.

Building [3, 2, 5, 1, 4] with a stack​

We can follow the algorithm one value at a time.

Insert 3​

The stack is empty, so 3 becomes the root of the partial tree and the only right-spine node.

Stack: [3]
Tree: 3

Insert 2​

The new value 2 is smaller than the stack top 3, so pop 3. The popped node becomes the left child of 2.

The stack is now empty, so 2 becomes the root of the partial tree:

    2
   /
  3

The stack becomes:

Stack: [2]

The in-order traversal of this partial tree is 3, 2, which is exactly the processed prefix.

Insert 5​

The new value 5 is larger than 2, so no node is popped. The surviving stack node 2 receives 5 as its right child:

    2
   / \
  3   5

The stack becomes:

Stack: [2, 5]

The right spine is now 2 followed by 5.

Insert 1​

The new value 1 is smaller than 5, so pop 5. It is also smaller than 2, so pop 2 as well.

The last popped node is 2, and it becomes the left child of 1. No node remains on the stack, so 1 becomes the root:

      1
     /
    2
   / \
  3   5

The stack is now:

Stack: [1]

This step is the central advantage of the stack method. The algorithm does not rescan the entire prefix to discover that 1 is the new minimum. It follows the right spine and removes exactly the nodes that 1 must move above.

Insert 4​

The new value 4 is larger than 1, so no nodes are popped. The remaining stack node 1 receives 4 as its right child:

      1
     / \
    2   4
   / \
  3   5

The final stack is:

Stack: [1, 4]

The final tree is identical to the tree produced by recursive minimum selection.

The pointer-update pattern​

The stack algorithm can be summarized with the following pseudocode:

last = empty
while stack is not empty and stack.top.value > x:
    last = stack.pop()

if stack is not empty:
    stack.top.right = x

x.left = last
stack.push(x)

This pseudocode assumes that x is a newly created node and that the implementation keeps a separate reference to the root when necessary.

The variable last records the most recently popped node. That node is the root of the entire group removed from the right spine, so it becomes the left child of the new node.

The surviving stack node, if one exists, becomes the parent of the new node through its right child. If the stack becomes empty, the new node becomes the root of the processed prefix.

A more explicit pointer interpretation is:

• last is initially empty because the new node may have no left subtree.
• Each pop moves a node off the right spine and updates last.
• After the loop, last identifies the root of the affected old suffix.
• Assigning x.left = last places that suffix before x in in-order traversal.
• Assigning stack.top.right = x places x after the surviving node in in-order traversal.

The exact node representation depends on the programming language, but the structural update is the same.

Why in-order order is preserved​

Suppose the new value $x$ is the next element in the array. Every previously processed node represents an earlier array position, so all of them must appear before $x$ in the final in-order traversal.

When larger right-spine nodes are popped, they form a suffix of the already processed right boundary. Making the last popped node the left child of $x$ places that affected suffix immediately before $x$ in the relevant part of the traversal.

If a node remains on the stack, making $x$ its right child also preserves order. The surviving node and its left subtree occur before the right child, so the new element appears after the older elements associated with that boundary.

The subtrees hanging from the popped nodes are not reordered internally. They remain intact and are moved as part of the affected subtree. Thus, the algorithm changes ancestry without changing the left-to-right sequence of array positions.

For the example, inserting 1 changes the partial tree from:

    2
   / \
  3   5

to:

      1
     /
    2
   / \
  3   5

The in-order sequence changes from 3, 2, 5 to 3, 2, 5, 1, exactly as required.

Why the heap property is preserved​

There are two cases to consider.

The new value is larger than the stack top​

If the stack top has value smaller than the new value $x$, assigning $x$ as its right child preserves the min-heap relationship. The surviving nodes above it on the right spine are also smaller than $x$ in the distinct-value case.

The new value is smaller than one or more stack nodes​

Every popped node has a value larger than $x$. Making those nodes descendants of $x$ places the smaller value above the larger values, which is exactly what the min-heap property requires.

If a node remains on the stack after popping, its value is smaller than $x$. Making it the parent of $x$ also preserves heap order.

Therefore, every insertion preserves the heap relation between the new node and the nodes whose relationships changed. Existing relationships outside the affected right spine remain untouched.

Why the stack construction is linear​

The inner loop may pop several nodes during one insertion, so it is natural to ask whether the algorithm could still take quadratic time. The answer comes from amortized analysis.

Each array element is pushed onto the stack exactly once. After an element is popped, it never returns to the stack, so each element can be popped at most once. Across an array of length $n$:

The comparisons and pointer assignments surrounding each stack operation take constant time. Consequently, the total construction time is:

The auxiliary stack contains at most one entry per input element, so its worst-case space usage is:

The tree nodes themselves also require $O(n)$ storage.

The important lesson is that a repeated inner loop does not automatically imply quadratic total time. Here, every iteration of the loop permanently removes one element from the stack, and no element can be removed more than once.

How the input determines the tree shape​

A Cartesian tree is not automatically balanced. Its shape is determined by the relationship between array positions and values.

If values increase from left to right, the first value is the smallest and becomes the root. Later values tend to form a right chain:

[1, 2, 3, 4]

The shape is:

1
 \
  2
   \
    3
     \
      4

If values decrease from left to right, the last value is the smallest and becomes the root. The result is a left chain:

[4, 3, 2, 1]

The shape is:

      1
     /
    2
   /
  3
 /
4

These are highly unbalanced trees. A Cartesian tree does not perform rotations simply to control height. Its shape follows directly from the array's value pattern.

For [3, 2, 5, 1, 4], the global minimum 1 appears at index 3, so it divides the array into a three-element left interval and a one-element right interval. The left interval has its own minimum 2, which creates the next level of the structure.

This recursive interval decomposition is also reflected in the stack algorithm: a new small value can rise above a suffix of the current right spine, while a new large value simply extends that spine.

Range minimum queries and lowest common ancestors​

A range minimum query asks for the minimum value in a contiguous section of an array. In [3, 2, 5, 1, 4], the range from index 0 through index 2 is [3, 2, 5], whose minimum is 2.

The Cartesian tree gives this minimum an ancestor interpretation. For a range with endpoint positions $i$ and $j$, the minimum is the lowest common ancestor of the nodes representing those endpoints:

Here, $\operatorname{RMQ}$ denotes the range minimum, and $\operatorname{LCA}$ denotes the lowest common ancestor.

Why does this work? The in-order invariant means that the nodes between positions $i$ and $j$ form the relevant contiguous interval. The heap invariant means that the smallest node in that interval rises above the other nodes in the corresponding subtree region. The first ancestor shared by the two endpoint paths is therefore the minimum of the range.

For the full range from 3 through 4, the endpoint nodes are the nodes containing 3 and 4. Their lowest common ancestor is 1, which is the minimum of the full array.

For the range [3, 2, 5], the endpoint nodes are 3 and 5. Their lowest common ancestor is 2, which is the minimum of that range.

The correspondence is easiest to see for distinct values. If equal values are allowed, the implementation must use a consistent tie-breaking rule when deciding which equal minimum becomes the ancestor.

Range examples from the tree​

Assign positions to the example array:

index:  0  1  2  3  4
value:  3  2  5  1  4

The tree relationships are:

1 at index 3 is the root
2 at index 1 is its left child
4 at index 4 is its right child
3 at index 0 is the left child of 2
5 at index 2 is the right child of 2

Now consider several ranges.

Range from index 0 to index 2​

The values are [3, 2, 5]. The endpoints are the nodes containing 3 and 5. Their lowest common ancestor is 2, so the range minimum is 2.

Range from index 1 to index 2​

The values are [2, 5]. The node containing 2 is an ancestor of the node containing 5, so their lowest common ancestor is 2. The range minimum is again 2.

Range from index 2 to index 4​

The values are [5, 1, 4]. The endpoint nodes are 5 and 4. Their lowest common ancestor is 1, which is the minimum of the range.

Range from index 3 to index 4​

The values are [1, 4]. The node containing 1 is an ancestor of the node containing 4, so the lowest common ancestor is 1, the range minimum.

The tree does not replace the array's order. Instead, it represents interval minima as ancestor relationships.

Why the right spine is sufficient​

The right spine is enough because the new element is appended at the right edge of the processed prefix. A new value cannot suddenly require arbitrary interior nodes to be rearranged. Any necessary change must be reached by following right-child links from the current root.

Suppose the current right spine has increasing values from top to bottom. If the new value $x$ is larger than the last spine value, it can be attached below that value as its right child. The existing spine remains valid.

If $x$ is smaller than the last spine value, that last node can no longer remain above $x$ on the right boundary. It is popped. The algorithm continues toward the root until it finds a node smaller than $x$ or reaches the top.

The final popped node is the nearest larger subtree that $x$ must absorb as its left subtree. Earlier popped nodes are already arranged inside that subtree. This is why a single variable such as last is sufficient to reconnect the affected structure.

The stack is therefore not an arbitrary collection of recent values. It is a compact representation of the only tree path that can change when the array grows from the right.

Direct construction versus stack construction​

Both methods implement the same Cartesian-tree definition, but they view the work differently.

The direct recursive method asks:

What is the minimum of this interval, and how should the interval split around it?

The stack method asks:

As the interval grows by one element, which nodes on the current right boundary are no longer allowed to remain above the new value?

The first method repeatedly searches intervals from scratch. The second maintains enough information incrementally so that every node is pushed once and popped at most once.

When the same heap convention and tie-breaking rule are used, both methods produce the same tree.

Connection to Treaps​

A Treap combines binary-search-tree order on keys with heap order on priorities. A Cartesian tree has the same two-dimensional structure when array positions serve as the in-order keys and array values serve as heap priorities.

In a Cartesian tree:

• Position determines in-order placement.
• Value determines heap placement.

In a Treap:

• Key determines binary-search-tree order.
• Priority determines heap placement.

A Treap is therefore a Cartesian tree with random priorities, using key order for the in-order dimension and priority order for the heap dimension. With a min-heap priority convention, smaller priorities rise toward the root. With a max-heap convention, larger priorities rise instead.

The word random describes how priorities are selected; it does not change the basic structural idea. Once keys and priorities are fixed, the two ordering rules determine the tree shape, subject to the chosen convention for equal priorities.

This connection shows that the Cartesian-tree pattern is broader than one array-construction technique. The central design is a structure with two simultaneous orders: one order controls traversal position, and another controls ancestry.

Practical implementation checklist​

When implementing a Cartesian tree, make the following decisions explicit.

Store positions as well as values​

The range-minimum interpretation depends on knowing which array position each node represents. A node should therefore store both its value and its index, or preserve the index through another mechanism.

Choose the heap convention​

This article uses a min Cartesian tree, where a parent is smaller than its children. A max Cartesian tree can be built by reversing the comparison used by the stack and the heap invariant.

Choose a tie-breaking rule​

The example contains distinct values, so every interval minimum is unambiguous. For repeated values, decide whether the stack should pop on > or on >=. Those choices produce different valid shapes because equal values can occupy different ancestor positions.

The important requirement is consistency. The recursive construction and the stack construction must use the same rule if they are expected to produce identical pointer structures.

Keep the root reference accurate​

If the new value pops every node currently on the stack, the new node becomes the root of the processed prefix. A complete implementation must update its root reference in that case.

Test both invariants​

After construction, test the in-order traversal and heap order separately. For the example, the expected in-order output is:

3, 2, 5, 1, 4

The expected parent comparisons are:

1 < 2
1 < 4
2 < 3
2 < 5

Testing both properties helps distinguish a traversal-order bug from a pointer-assignment bug.

A compact mental model​

A useful way to remember the stack algorithm is:

Scan from left to right, maintain an increasing right spine, pop larger nodes when a smaller value arrives, attach the popped subtree on the left, attach the new node on the right of the surviving node, and push the new node.

For [3, 2, 5, 1, 4], the stack snapshots are:

read 3: [3]
read 2: [2]
read 5: [2, 5]
read 1: [1]
read 4: [1, 4]

The snapshots do not show every child pointer, but they show the changing right boundary. The entries removed from the stack are not discarded. They become part of the new node's left subtree.

That distinction is essential. A pop means that a node leaves the right spine, not that it leaves the tree. Every input element remains represented exactly once.

Final takeaways​

A Cartesian tree is defined by two invariants:

• Its in-order traversal reproduces the input array.
• Its parent values satisfy the min-heap property.

For [3, 2, 5, 1, 4], the tree has 1 at the root, 2 and 4 as its children, and 3 and 5 beneath 2. An in-order traversal returns the original sequence exactly.

The recursive definition is straightforward: choose the minimum of an interval as its root and recurse on the two sides. However, repeatedly scanning intervals can require $O(n^2)$ time in the worst case.

A monotonic stack avoids that repeated work. It stores the current right spine, pops larger values when a smaller value arrives, and reconnects the affected nodes with a constant amount of pointer work per stack operation. Because each element is pushed once and popped at most once, total construction time is $O(n)$, with $O(n)$ auxiliary space.

The same structure gives a tree interpretation of range minima. For a range, the lowest common ancestor of its endpoint nodes is the range minimum, assuming a consistent Cartesian-tree definition and an unambiguous tie convention.

Finally, the connection to Treaps highlights the general design: one ordering controls in-order position, while another ordering controls heap ancestry. Cartesian trees make that dual-order relationship concrete, efficient, and useful for both array algorithms and tree-based data structures.