Cartesian Tree

Cartesian Tree is a derivative binary tree data structure in computation and algorithms constructed from an indexed sequence of numbers A[1 .. n] such that the tree simultaneously obeys the binary heap ordering property on element keys and preserves the original sequence index ordering under a symmetric in-order traversal. Introduced by French computer scientist Jean Vuillemin in 1980 within the geometric context of range searching on two-dimensional Cartesian coordinate sets, the structure maps each array entry (i, A[i]) to a planar point whose horizontal coordinate x = i governs left-to-right binary search tree placement and whose vertical coordinate y = A[i] governs parent-to-child min-heap priority.

Within computational complexity theory and combinatorial data structures, the Cartesian tree establishes a structural bijection between sequence range queries and tree topology problems. In a foundational 1984 paper, Harold N. Gabow, Jon Louis Bentley, and Robert Endre Tarjan demonstrated that the Range Minimum Query (RMQ) over any contiguous subarray A[l .. r] reduces directly to computing the Lowest Common Ancestor (LCA) of nodes l and r in the sequence's Cartesian tree. Because a Cartesian tree over n elements can be constructed in deterministic O(n) linear time using a monotonic stack and encoded succinctly in 2n + o(n) bits via balanced parentheses, it forms the algorithmic backbone of O(1)-time RMQ indexes, suffix tree and suffix array Lowest Common Prefix (LCP) navigation, and randomized binary search trees such as the treap.

Dual Heap and In-Order Sequence Invariants

Let A = (A[1], A[2], ..., A[n]) be a sequence of n comparable numerical values. Assuming all elements of A are distinct (or breaking ties deterministically by preferring smaller array indices), the min-Cartesian tree T(A) is the unique rooted binary tree on vertex set {1, 2, ..., n} satisfying two simultaneous invariants:

1. In-Order Index Invariant (Binary Search Tree on Indices): For every node i ∈ {1, ..., n}, every node j in the left subtree of i satisfies j < i, and every node k in the right subtree of i satisfies k > i. Consequently, a standard in-order traversal of T(A) visits the nodes in ascending index order 1, 2, ..., n, reconstructing the original sequence A.
2. Heap Priority Invariant (Min-Heap on Values): For every non-root node u with parent p(u), the array values satisfy A[p(u)] ≤ A[u] (and A[p(u)] < A[u] when keys are distinct). By induction, the root of T(A) is the index m = argmin_1≤i≤n A[i] of the global minimum element in the array.

Recursive Partitioning and Catalan Enumeration

The two invariants uniquely determine the topology of T(A) via recursive divide-and-conquer partitioning. Given a subarray A[l .. r] with 1 ≤ l ≤ r ≤ n, let m ∈ {l, ..., r} be the index of the minimum element in A[l .. r]. Because m must sit above all other indices in [l, r] by the min-heap invariant, m is the root of the subtree corresponding to A[l .. r]. By the in-order invariant, all indices in [l, m − 1] must lie in the left subtree of m, and all indices in [m + 1, r] must lie in the right subtree of m:

Although naive top-down construction requires O(n log n) time on average and O(n²) worst-case time on sorted inputs (where m = l at every step, producing a degenerate right-leaning chain of height n), bottom-up incremental insertion along the rightmost spine reduces construction to worst-case O(n) time. Furthermore, two permutations of {1, ..., n} yield isomorphic unlabeled Cartesian tree topologies only when their relative minimum structure coincides; the total number of distinct unlabeled binary tree shapes over n nodes is given by the n-th Catalan number:

Because each unlabeled binary tree topology can be encoded in 2n bits using a balanced-parenthesis string or DFUDS (Depth-First Unary Degree Sequence) representation, a Cartesian tree supports constant-time RMQ evaluation without storing the explicit keys of A once the topology is built.

Right-Spine Incremental Insertion Algorithm

To construct T(A) in deterministic O(n) time, indices i = 1, 2, ..., n are inserted sequentially from left to right. Because index i is rigorously larger than all previously inserted indices {1, 2, ..., i − 1}, the in-order invariant requires that node i be placed as the bottom-most node on the rightmost path (right spine) of the current tree T(A[1 .. i − 1]).

To restore the min-heap invariant when inserting A[i], the algorithm maintains an explicit monotonic stack S containing the sequence of indices along the current right spine, ordered from the root at the bottom of the stack to the most recently inserted index i − 1 at the top of the stack. Along this right spine, array values are monotonically increasing from bottom to top. When processing index i:

1. Right-Spine Ascent (Stack Pop Loop): While the stack S is non-empty and the value at the top of the stack exceeds the new value (A[top(S)] > A[i]), pop the top node v ← pop(S) and record v as the most recently popped node last_popped.
2. Subtree Re-Parenting: After the loop terminates, every popped node has a key larger than A[i] and an index smaller than i. The last popped node lastpopped (which was the highest ancestor on the right spine with A[v] > A[i]) retains its entire subtree of smaller indices and becomes the left child of the new node i: left(i) ← lastpopped.
3. Spine Attachment and Push: If the stack S is still non-empty, its current top node u = top(S) satisfies A[u] ≤ A[i] and u < i, so i is attached as the right child of u: right(u) ← i. Finally, push i onto S as the new terminus of the right spine.

Amortized Complexity and Parent-Pointer Construction

Every index i ∈ {1, ..., n} is pushed onto the right-spine stack S once and popped from S at most once during the entire scan. When a node v is popped because A[v] > A[i], v is moved into the left subtree of i and leaves the right spine permanently, never to be inspected again. By the accounting method of amortized analysis, the total number of comparisons and pointer assignments across all n insertions is bounded by 2n − 1, yielding worst-case O(n) time and O(n) auxiliary workspace.

The Gabow–Bentley–Tarjan Reduction

The primary algorithmic application of Cartesian trees is the bidirectional reduction between the Range Minimum Query (RMQ) problem on arrays and the Lowest Common Ancestor (LCA) problem on trees, established by Gabow, Bentley, and Tarjan (1984) and refined by Bender and Farach-Colton (2000). For any query interval [l, r] with 1 ≤ l ≤ r ≤ n in array A, let u = LCA_T(A)(l, r) be the lowest common ancestor of nodes l and r in the Cartesian tree T(A):

• Because u is the lowest common ancestor of l and r in a binary tree satisfying the in-order index invariant, l lies in the left subtree of u (or l = u) and r lies in the right subtree of u (or r = u), which implies l ≤ u ≤ r.
• Moreover, every index k ∈ [l, r] must be a descendant of u in T(A), because splitting [l, r] at any ancestor above u would separate l and r into distinct subtrees.
• By the min-heap invariant, u has the smallest array value among all nodes in its subtree, and therefore among all indices in [l, r]:

Conversely, any rooted tree T on n vertices can be converted via an Euler tour of length 2n − 1 into a depth array D[1 .. 2n − 1] in which consecutive entries differ by +1 or −1; the LCA of two vertices in T is then the minimum-depth entry between their first Euler-tour occurrences. Partitioning D into blocks of size b = ⌊(log₂ n) / 2⌋ and precomputing all 2^b−1 = O(√n) normalized ±1 block Cartesian tree types (the Four Russians technique) yields O(n) preprocessing time and worst-case O(1) query time.

Treaps, Suffix Arrays, and Levcopoulos–Petersson Adaptive Sorting

When the first coordinate x_i of a point set is a dynamic dictionary key and the second coordinate y_i is drawn independently and uniformly at random from [0, 1], the resulting Cartesian tree is a treap (tree + heap), formalized by Raimund Seidel and Cecilia R. Aragon in 1996. Because every rank position among k keys is equally likely to receive the minimum random priority y, a treap maintains expected depth O(log n) with high probability under dynamic insertions and deletions via single tree rotations.

In full-text string indexing, combining a suffix array SA[1 .. n] with its Longest Common Prefix array LCP[1 .. n − 1] and the Cartesian tree of the LCP array yields an Enhanced Suffix Array (Abouelhoda, Kurtz, & Ohlebusch, 2004). Each internal node of the LCP Cartesian tree corresponds to an explicit internal node (lcp-interval) of the suffix tree, supporting bottom-up and top-down suffix tree traversals in linear space alongside compressed Burrows–Wheeler transform indexes. In adaptive comparison sorting, Christos Levcopoulos and Ola Petersson (1989) showed that constructing the Cartesian tree of an input sequence and repeatedly extracting the minimum from a priority queue of tree roots sorts sequences with k local extrema in O(n log k) comparisons, matching the Shannon entropy bound for presorted oscillations.

Why does an in-order traversal of a Cartesian tree always reproduce the original array order?

By construction, whenever a subarray A[l .. r] is partitioned around the index m of its minimum value, all elements at indices l .. m − 1 are placed in the left subtree of m and all elements at indices m + 1 .. r are placed in the right subtree of m. Because an in-order traversal recursively visits the left subtree, then the root m, and then the right subtree, inductive expansion visits the indices in ascending sequence 1, 2, ..., n.

How can a Cartesian tree answer Range Minimum Queries in 2n + o(n) bits without storing the original array?

Because RMQ_A(l, r) returns the array index m of the minimum element rather than its numerical value A[m], the answer depends only on the tree topology of T(A). Johannes Fischer and Volker Heun (2011) proved that encoding the Cartesian tree topology as a 2n-bit DFUDS balanced-parenthesis string—augmented with o(n)-bit rank/select directories—allows the i-th in-order node and the LCA of any two nodes to be located in worst-case O(1) time without accessing A.

1. Vuillemin, J. (1980). "A unifying look at data structures." Communications of the ACM, 23(4), 229–239. https://doi.org/10.1145/358841.358852
2. Gabow, H. N., Bentley, J. L., & Tarjan, R. E. (1984). "Scaling and related techniques for geometry problems." Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC '84), 135–143. https://doi.org/10.1145/800057.808675
3. Seidel, R., & Aragon, C. R. (1996). "Randomized search trees." Algorithmica, 16(4–5), 464–497. https://doi.org/10.1007/BF01940876
4. Bender, M. A., & Farach-Colton, M. (2000). "The LCA problem revisited." Proceedings of the 4th Latin American Symposium on Theoretical Informatics (LATIN 2000), LNCS Vol. 1776, 88–94. https://doi.org/10.1007/10719839_9
5. Fischer, J., & Heun, V. (2011). "Space-efficient preprocessing schemes for range minimum queries on static arrays." SIAM Journal on Computing, 40(2), 465–492. https://doi.org/10.1137/090779759