Cartesian Tree: Where Order Meets the Heap

A Cartesian tree is a binary tree built from a sequence of values. It combines two different kinds of structure:

1. In-order order: reading the tree with an in-order traversal reproduces the original sequence order.
2. Heap order: every parent satisfies a heap relationship with its children according to the values stored in the nodes.

This combination is the central idea. A Cartesian tree is not merely a binary search tree, because the sequence positions determine the in-order arrangement. It is not merely a heap, because the tree must also preserve the original left-to-right order of the input sequence.

The result is a useful bridge between arrays and trees. An array gives direct positional order but does not explicitly represent hierarchical relationships. A heap gives value priority but does not preserve the original sequence order in the same way. A Cartesian tree preserves both at once.

This article explains the shape and invariants of a Cartesian tree, describes a recursive way to understand its structure, shows a linear-time construction using a monotonic stack, and explains why Cartesian trees appear in applications such as range minimum queries, lowest common ancestors, and Treaps.

1. The basic problem: preserving two orders​

Suppose the input sequence is:

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

A Cartesian tree must satisfy two independent requirements.

In-order order​

If we traverse the resulting binary tree in this order:

left subtree → node → right subtree

we must visit the values in exactly the original order:

4, 2, 6, 1, 5, 3

This means that the node containing 4 appears before the node containing 2, the node containing 2 appears before 6, and so on. The tree cannot arbitrarily rearrange the sequence.

Heap order​

The values must also satisfy a heap property. For a min Cartesian tree, each parent has a value less than or equal to the values of its children. For a max Cartesian tree, each parent has a value greater than or equal to the values of its children.

For the sequence above, consider a min Cartesian tree. The smallest value is 1, so it naturally becomes the root. Values before 1 form the left side of the tree, and values after 1 form the right side. One representation is:

        1
       / \
      2   3
     / \  /
    4  6 5

The in-order traversal is:

4, 2, 6, 1, 5, 3

The heap condition also holds: 1 is smaller than its descendants, 2 is smaller than 4 and 6, and 3 is smaller than 5.

The exact drawing is less important than the two invariants. A valid Cartesian tree must preserve the input order through in-order traversal and satisfy the selected heap order through parent-child relationships.

2. The recursive view of the shape​

The defining properties give a direct recursive description of a min Cartesian tree.

Given a sequence segment:

1. Find the minimum value in the segment.
2. Make that value the root of the segment's tree.
3. Recursively build the left subtree from the elements before the minimum.
4. Recursively build the right subtree from the elements after the minimum.

For the sequence:

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

The minimum is 1, at position four. Therefore:

• The left subtree uses [4, 2, 6].
• The right subtree uses [5, 3].

The minimum of [4, 2, 6] is 2, so 2 becomes the root of the left subtree:

    2
   / \
  4   6

The minimum of [5, 3] is 3, so 3 becomes the root of the right subtree:

  3
 /
5

Combining these pieces gives the complete tree.

This recursive definition makes the shape easy to understand, but a direct implementation that repeatedly scans for the minimum can be expensive. If every recursive step scans a large part of the sequence, the total work can become quadratic in the worst case. The monotonic-stack construction avoids those repeated scans and builds the tree in O(n) time.

The recursive view is still valuable even when it is not the implementation used in practice. It explains why every subtree corresponds to a contiguous segment and why the smallest value in that segment must be at the subtree root.

3. Why position matters as much as value​

It is useful to distinguish a Cartesian tree from other familiar trees.

A binary search tree organizes nodes according to key comparisons between values. Values in the left subtree follow one ordering rule, and values in the right subtree follow another. A Cartesian tree instead treats the input sequence as a fixed left-to-right layout. The in-order traversal must reproduce that layout exactly.

A heap organizes values by priority, but its shape is not generally determined by the original order of an array in the same way. A Cartesian tree adds the positional constraint: nodes cannot move past one another in in-order order.

For example, in the sequence:

[7, 3, 8]

The minimum Cartesian tree must have 3 as its root. Because 7 appears before 3, it must be in the left subtree. Because 8 appears after 3, it must be in the right subtree:

    3
   / \
  7   8

Changing the shape to make 7 or 8 the root would violate min-heap order. Moving 7 to the right side would violate in-order sequence order. Both restrictions are active at the same time.

This is why the word Cartesian is useful here: the structure represents a sequence of points with one coordinate supplied by position and another supplied by value. The tree shape reflects how those two dimensions interact, while the two invariants provide the precise definition needed for algorithms.

4. Min and max Cartesian trees​

The phrase heap order does not by itself specify whether the root is the minimum or the maximum. There are two common versions.

Min Cartesian tree​

For a min Cartesian tree:

parent.value ≤ child.value

The minimum element of the entire sequence becomes the root. In any subtree corresponding to a contiguous sequence segment, the minimum of that segment becomes the subtree root.

Min Cartesian trees are especially natural when discussing range minimum queries, because a range's minimum can be connected to an ancestor relationship in the tree.

Max Cartesian tree​

For a max Cartesian tree:

parent.value ≥ child.value

The maximum element of the entire sequence becomes the root. The same recursive and stack ideas apply, with the comparison direction reversed.

The construction algorithm is therefore not tied to only one version. The key decision is the comparison used to maintain the monotonic stack. A stack that is monotonic in one direction builds a min-oriented tree; reversing the comparison builds the corresponding max-oriented tree.

The choice between min and max should be made according to the query or application. If the important operation asks for minimum values, use the min form. If it asks for maximum values, use the max form. The structural reasoning is the same in both cases.

5. A small structural example​

Consider the sequence:

[5, 2, 4, 1, 3]

For a min Cartesian tree, 1 is the root because it is the smallest value:

        1
       / \
      2   3
     / \
    5   4

Check the in-order traversal:

1. Traverse the left subtree of 1.
2. In that subtree, visit 5, then 2, then 4.
3. Visit 1.
4. Visit the right subtree, which contains 3.

The result is:

5, 2, 4, 1, 3

Check heap order:

• 1 is smaller than 2 and 3.
• 2 is smaller than 5 and 4.

Now observe the shape. The values before the global minimum 1 form the entire left subtree, while the values after it form the entire right subtree. This is always true because in-order order prohibits nodes from crossing the root's position.

The same observation applies recursively. The left subtree covers the contiguous interval before the root position, and the right subtree covers the contiguous interval after it. Within each interval, the minimum again becomes the local root.

6. The monotonic-stack idea​

The efficient construction processes the sequence from left to right. At every point, it maintains a stack of nodes that can still participate in the tree being formed.

For a min Cartesian tree, the stack is maintained according to a monotonic value relationship. One useful way to describe the process is:

1. Create a node for the next value.
2. Remove stack nodes that are incompatible with the new value's position in the min-heap structure.
3. The last removed node becomes part of the new node's left subtree.
4. If a node remains on the stack, the new node becomes its right child or the root of its existing right-side structure.
5. Push the new node onto the stack.

The exact pointer assignments are easier to understand through an example.

Use the sequence:

[5, 2, 4, 1, 3]

We process one value at a time.

Process 5​

The stack is empty. Create the node 5 and push it:

stack: [5]

The current partial tree is simply:

5

Process 2​

The new value 2 is smaller than 5. To maintain min-heap order, 5 cannot remain above 2. Pop 5 from the stack. The popped node becomes the left subtree of 2:

  2
 /
5

Push 2:

stack: [2]

The in-order sequence is still 5, 2, because 5 is to the left of 2.

Process 4​

The new value 4 is greater than the top value 2, so no node must be popped. The new node belongs after 2 in in-order order, making it the right child of 2:

  2
 / \
5   4

Push 4:

stack: [2, 4]

Process 1​

The new value 1 is smaller than 4, so pop 4. It is also smaller than 2, so pop 2. The last popped node, 2, becomes the left subtree of 1:

    1
   /
  2
 / \
5   4

The stack is now empty. Push 1:

stack: [1]

Notice why the last popped node becomes the left child. The popped nodes form a region immediately to the left of the new value in sequence order. The last popped node is the root of that entire region, and its existing left and right links preserve the internal structure.

Process 3​

The new value 3 is greater than 1, so no nodes are popped. It becomes the right child of 1:

    1
   / \
  2   3
 / \
5   4

The final stack is:

stack: [1, 3]

The result is the desired Cartesian tree.

7. The right-spine interpretation​

Another useful way to understand the stack is to view it as a path along the current tree's right boundary. Because the input is processed from left to right, every new node arrives after all earlier nodes in in-order order. It therefore interacts with the current right side of the partial tree.

If the new value is large enough, it can be attached near the bottom of that right boundary. If the new value is smaller, it rises above one or more nodes on the boundary. The nodes it displaces become part of its left subtree.

This explains why the algorithm does not need to search the entire partial tree. Only the right boundary can be affected by a new value arriving at the far right of the sequence. The monotonic stack stores exactly the candidates on that boundary that may need to be compared or reconnected.

For the sequence [5, 2, 4, 1, 3], the stack changes as follows:

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

The stack is not the full tree. It is a compact representation of the currently exposed path. Nodes that have been removed from the stack remain in the tree; they simply no longer lie on the boundary that future values can modify.

This boundary perspective is often the easiest way to recognize when a monotonic stack can solve a construction problem. The algorithm does not repeatedly reconsider every earlier item. It keeps only the active frontier and permanently settles nodes once they are popped.

8. Why the stack construction is linear​

The monotonic-stack method runs in O(n) time because every input node is pushed onto the stack once and popped from the stack at most once.

A single iteration may pop several nodes, so an individual iteration can take more than constant time. However, the total number of pops over the entire construction cannot exceed the number of nodes. The total work is therefore proportional to:

number of pushes + number of pops = O(n)

The auxiliary stack contains at most n nodes, so the additional space is O(n). The tree itself also contains n nodes, meaning the complete representation requires O(n) space.

This is a standard amortized-analysis pattern. Looking at one iteration in isolation can make the repeated popping seem expensive. Looking at the entire run reveals that a node cannot be popped repeatedly: once popped, it leaves the stack permanently.

The contrast with the recursive minimum-search description is important:

• Repeatedly scanning segments can take O(n²) in an unfavorable shape.
• The monotonic-stack method constructs the same conceptual tree in O(n).

The shape may be highly unbalanced, but the construction time remains linear because it depends on stack events rather than the height of the final tree.

The construction also avoids needing a separate minimum-search data structure during the build. Each comparison is made only when a node is pushed or removed from the active frontier. That is the source of the efficiency, not any assumption that the resulting tree is balanced.

9. Understanding pointer updates​

A typical implementation keeps two references for each node:

• left: the root of its left subtree
• right: the root of its right subtree

When processing a new node, let last be the final node removed from the stack.

The new node is connected to last as its left child:

newNode.left = last

If the stack is not empty after popping, let the remaining top be parent. The new node is placed after parent in in-order order, so it becomes the right child associated with that position:

parent.right = newNode

The important detail is that the new node may replace the previous right child of parent. That previous right child is not discarded; it becomes part of the new node's left subtree through last.

Conceptually, a new smaller value cuts into the right edge of the partial tree. Nodes that are too large to remain above it are lifted below it on the left. The remaining stack top becomes the new node's parent on the right side.

For the earlier example, when processing 1:

• 4 is popped first.
• 2 is popped second.
• 2 becomes 1's left child.
• Since the stack is empty, 1 becomes the root.

When processing a value that pops some nodes but leaves others, the remaining top receives the new node as its right child. This is how the algorithm preserves both value order and sequence order.

A common implementation pattern initializes last to null for each input value. If no node is popped, the new node gets an empty left subtree. If one or more nodes are popped, last points to the root of the complete region that must move below the new node.

10. Ties and uniqueness​

Repeated values require a consistent tie policy. If two values are equal, both can satisfy a non-strict heap relation such as:

parent.value ≤ child.value

But different choices about whether an equal value should trigger a pop can produce different valid tree shapes. The in-order sequence and heap property may still hold, while the exact arrangement of equal-valued nodes differs.

Therefore, an implementation should choose one comparison policy and use it consistently. For example, it may pop only when the stack top is strictly greater than the incoming value, or it may also pop equal values. The choice affects which equal-valued node becomes structurally higher.

The general lesson is that a Cartesian tree's shape is unambiguous when values are distinct. With duplicates, the heap condition alone may not determine one unique shape unless a tie-breaking convention is specified.

This is not a problem for the linear-time method, but it is an important implementation detail. A recursive definition that says choose the minimum also needs a rule for which occurrence of the minimum to choose when the minimum appears more than once.

The tie policy should also be reflected in explanations of RMQ and LCA. When several positions share the same minimum value, the LCA identifies the selected representative according to the construction's structural convention. The minimum value remains correct, but the identity of the minimum node depends on the tie rule.

11. Cartesian trees and range minimum queries​

A range minimum query, commonly abbreviated RMQ, asks for the minimum value in a selected contiguous range of a sequence.

For example, given:

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

an RMQ over positions containing [2, 4, 1] asks for the minimum of that range, which is 1.

The Cartesian tree is relevant because every subtree corresponds to a contiguous interval of the original sequence under in-order order. More specifically, the subtree rooted at a node covers the sequence positions represented by that node and all of its descendants. Since the tree is min-ordered, the root of that subtree is the minimum value of that interval.

There is also a central relationship between a range minimum and a lowest common ancestor. Consider two positions in the original sequence. Their corresponding nodes in the min Cartesian tree have a lowest common ancestor, or LCA. That ancestor represents the minimum over the interval between the two positions, subject to the chosen tie-handling convention.

The intuition is structural:

• The in-order traversal places the two positions in their original left-to-right order.
• Their lowest common ancestor is the first tree node whose represented region contains both positions.
• That region covers the sequence interval between them.
• Heap order makes the ancestor's value the minimum for that region.

Thus, an RMQ problem on the array can be connected to an LCA problem on the Cartesian tree. The two problems have different surface forms but share the same underlying structure after the Cartesian tree is built.

The connection is valuable because it translates a value query over a contiguous array range into an ancestor query over a tree. The Cartesian tree supplies the structural bridge; the exact method used to answer the resulting LCA queries is a separate concern.

12. A visual RMQ-to-LCA example​

Use the min Cartesian tree for:

[5, 2, 4, 1, 3]

        1
       / \
      2   3
     / \
    5   4

Suppose the query covers the values at positions corresponding to 5 and 4. Their nodes are both inside the left subtree. Their lowest common ancestor is 2.

The original interval from 5 to 4 is:

[5, 2, 4]

Its minimum is 2, which is exactly the value at their LCA.

Now consider the positions corresponding to 5 and 3. Their paths meet at the root 1. The interval between them is the complete sequence:

[5, 2, 4, 1, 3]

Its minimum is 1, matching the root.

This example illustrates why the in-order invariant is essential. Without the original positional order, an ancestor would not necessarily represent a contiguous interval in the input sequence, and the RMQ interpretation would fail.

The same idea applies to two adjacent positions, to a range contained entirely within one subtree, and to a range that crosses the root of a subtree. In each case, the first common ancestor of the endpoint nodes represents the smallest tree region containing the whole interval.

13. Cartesian trees and Treaps​

A Treap combines two priorities in a randomized binary search tree. One ordering is based on keys, and another is based on heap priorities. The name reflects the combination of tree and heap.

A Cartesian tree has a closely related structure: one dimension supplies the in-order arrangement, and the other supplies heap order. In a Treap, the keys determine the in-order sequence while the priorities determine the heap structure. If the keys are viewed as an ordered sequence and the priorities as the values used for heap comparisons, the resulting shape follows the Cartesian-tree idea.

This connection explains why Cartesian trees are relevant when studying Treaps. The same conceptual pattern appears in both:

• One property preserves sorted or sequence order.
• Another property selects which node rises above which others.

For a Cartesian tree built from an array, the positions are fixed by the input order and the values determine the heap relationship. For a Treap, keys determine in-order order and priorities determine heap order. The roles are analogous even though the surrounding use cases differ.

This perspective also helps explain why rotations are meaningful in Treap implementations. Rotations can change the shape while preserving the binary-search-tree ordering of keys and restoring or maintaining the heap ordering of priorities. The Cartesian-tree viewpoint emphasizes that a valid structure is defined by two simultaneous invariants rather than by shape alone.

The connection should not obscure the distinction between the structures. A Cartesian tree is constructed from a fixed sequence and its selected values. A Treap is used as a dynamic tree in which keys and priorities define the two orderings. The common idea is the coexistence of an in-order constraint and a heap constraint.

14. Shape and balance​

Cartesian trees do not automatically have a balanced shape. Their structure depends on the relative arrangement of the sequence values.

A sequence whose values are already increasing can produce a long, one-sided shape for a min Cartesian tree. For example:

[1, 2, 3, 4]

The minimum is the first element, so the tree becomes a chain extending to the right:

1
 \
  2
   \
    3
     \
      4

A decreasing sequence:

[4, 3, 2, 1]

produces a chain extending to the left:

      1
     /
    2
   /
  3
 /
4

A sequence whose minimum lies near the middle can produce a more divided shape. However, the Cartesian-tree definition itself does not promise balance.

This observation is important for complexity discussions. The monotonic-stack construction remains O(n) even when the resulting tree is a chain. But later operations that depend on following tree height may behave differently depending on the shape. The tree's shape is an encoded summary of the input order and values, not a separately balanced search structure.

The recursive description makes this especially clear. If the minimum repeatedly occurs at one end of each remaining interval, one side of the tree keeps containing almost the entire interval. If the minimum repeatedly divides intervals into more comparable pieces, the tree appears more balanced. The algorithm does not impose either outcome; the sequence determines it.

15. A correctness perspective​

The stack algorithm can be understood through preservation of the two invariants.

Preserving in-order order​

Nodes are processed from left to right in the original sequence. A new node always represents a later position than every node already processed. Therefore, it must be attached on the right side of the existing partial structure, except that previously formed right-side nodes may be moved into its left subtree when the new value becomes structurally higher.

Those moved nodes still remain before the new node in in-order traversal, so their sequence positions are preserved.

Preserving heap order​

For a min Cartesian tree, a new value that is smaller than stack-top values cannot remain below those larger values. The algorithm pops them until the remaining stack top has a value that can be above the new node, or until the stack is empty.

The popped nodes become descendants of the new node, so the new smaller value is above them. The remaining stack nodes satisfy the required comparison with the new node according to the monotonic-stack condition.

Preserving internal structure​

The popped nodes are not rebuilt from scratch. Their existing links are retained inside the subtree attached to the new node. This means the algorithm changes only the necessary boundary connections while preserving the structure already established for earlier values.

Together, these facts explain why the final tree has the original sequence as its in-order traversal and satisfies heap order.

A useful proof strategy is induction over the processed prefix. Assume that the current partial tree represents exactly the processed prefix in in-order order and satisfies heap order. When the next value arrives, only the exposed right boundary can need modification. Popping removes nodes that the new value must dominate; attaching the final popped subtree on the left preserves order; attaching the new node below the remaining stack top preserves the boundary's order. The same two invariants therefore hold for the longer prefix.

16. Implementation-oriented pseudocode​

The following pseudocode describes a common min-oriented construction. It assumes that each input element has a corresponding node and that the selected comparison policy handles ties consistently.

stack = empty stack
root = null

for value in sequence from left to right:
    current = new Node(value)
    last = null

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

    current.left = last

    if stack is not empty:
        stack.top.right = current
    else:
        root = current

    stack.push(current)

The exact use of > represents one strict tie policy for a min Cartesian tree. A different policy may use a non-strict comparison, but the choice must be intentional and consistent.

The variable last records the final node removed. If several nodes are popped, the last one is the root of the already-built region that must become the new node's left subtree. The stack top after popping is the closest surviving node that can become the new node's parent on the right side.

At the end of the scan, root points to the root of the Cartesian tree. The stack itself contains a path or right spine of the resulting structure, although the complete tree is connected through all the stored child pointers.

For a max Cartesian tree, reverse the value comparison so that larger values rise toward the root. The same pointer pattern remains: retain the final popped subtree as the new node's left child, connect the new node to the surviving stack top when one exists, and update the root when the stack becomes empty.

17. Testing a Cartesian-tree implementation​

A practical implementation should test both structural invariants rather than checking only a few expected pointers.

Test the in-order traversal​

Run an in-order traversal of the constructed tree and compare the resulting sequence with the original input. They must match exactly, including repeated values and their order.

Test heap order​

For every node:

• In a min tree, verify that each child has a value at least as large as the parent according to the chosen equality policy.
• In a max tree, verify that each child has a value at most as large as the parent.

Test edge cases​

Useful cases include:

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

An empty sequence should produce no root. A one-element sequence should produce a single node with no children. Increasing and decreasing sequences test highly unbalanced shapes. Repeated values test tie handling.

Test the root​

For a min Cartesian tree, the root should contain a minimum value of the complete sequence. For a max Cartesian tree, it should contain a maximum value.

These checks are simple but powerful. If the in-order traversal is wrong, a pointer update likely misplaced a node. If heap order is wrong, the popping comparison or parent assignment is likely incorrect.

For additional confidence, compare the stack construction with the recursive definition on small sequences. Build the tree by repeatedly selecting a segment minimum, using the same tie rule, and compare the structural properties or serialized shape. This can expose errors in how the final popped node is connected, especially when several consecutive values are popped.

18. Common misconceptions​

A Cartesian tree is just a heap​

Not quite. A heap condition alone does not preserve the input sequence as an in-order traversal. The Cartesian tree requires both properties.

The root is always the first element​

The root is the minimum for a min Cartesian tree or the maximum for a max Cartesian tree. Its position depends on where that extreme value occurs in the sequence.

The tree must be balanced​

No. Increasing or decreasing input can create a chain. The construction is linear-time even when the shape is unbalanced.

The recursive definition is the construction algorithm​

The recursive definition explains the shape, but directly finding a minimum in every subrange can repeat work. The monotonic-stack method uses the same structural idea more efficiently and achieves O(n) construction time.

Equal values have only one possible shape​

Without a tie-breaking rule, equal values may admit multiple valid arrangements. A consistent comparison policy is part of a precise implementation.

The stack contains every part of the tree​

The stack contains the active boundary, not the entire tree. Nodes that are popped remain connected in the completed structure. They are removed only from the set of candidates that future input values may modify.

Linear construction means the tree is balanced​

It does not. Linear construction comes from the push-once and pop-once accounting argument. The final height can still be large, because height depends on the input arrangement.

19. Practical takeaways​

The most important ideas can be summarized as follows:

1. A Cartesian tree is a binary tree derived from a sequence.
2. Its in-order traversal reproduces the original sequence order.
3. Its values satisfy a min-heap or max-heap relationship.
4. The root is the global minimum or maximum, depending on the chosen orientation.
5. Each subtree represents a contiguous interval of the original sequence.
6. A monotonic stack constructs the tree in O(n) time.
7. Each node is pushed once and popped at most once, which explains the linear bound.
8. The min version provides a structural connection between range minimum queries and lowest common ancestors.
9. The combination of sequence or key order with heap priority also explains the relationship to Treaps.
10. Duplicate values require a deliberate tie-breaking policy.
11. The tree may be highly unbalanced even though construction is linear.
12. Correctness is best checked through both in-order traversal and heap-order validation.

Cartesian trees are a compact example of how one structure can encode two kinds of order simultaneously. The sequence determines where nodes appear from left to right, while the values determine which nodes rise toward the root. Once this dual viewpoint is clear, the recursive shape, the monotonic-stack construction, and the RMQ/LCA connection all follow from the same pair of invariants.

Conclusion​

A Cartesian tree sits at the intersection of arrays and heaps. It preserves the array's order through in-order traversal while imposing heap order on the values. The global minimum or maximum becomes the root, and the same rule applies recursively to every contiguous segment represented by a subtree.

The monotonic-stack construction turns this definition into a practical O(n) algorithm. By processing values from left to right, popping nodes that can no longer remain above the new value, and reconnecting the affected right spine, it builds the complete tree without repeatedly scanning for subrange extrema.

That structure is more than an interesting tree shape. In the min-oriented form, it links range minimum queries to lowest common ancestors. Its two-order design also provides a natural way to understand the relationship between Cartesian trees and Treaps. The central lesson is simple and broadly useful: when positional order and priority order must coexist, a Cartesian tree provides a direct structural representation of both.