Fact-checked by Grok 2 weeks ago

Cartesian tree

A Cartesian tree is a derived from a of distinct numbers, where each node stores a pair consisting of a position (or key) from the sequence and its corresponding value, such that the tree satisfies the property with respect to the positions (in-order traversal recovers the original sequence) and the min-heap (or max-heap) property with respect to the values (parent nodes have smaller or larger values than their children). The tree is uniquely determined by the sequence and can be constructed efficiently in linear time using a stack-based that processes the elements from left to right, maintaining the right spine of the tree. Introduced by Jean Vuillemin in 1980 as part of a unifying framework for data structures, the Cartesian tree combines properties of search trees and heaps, making it particularly useful in algorithmic applications. One of its primary applications is in solving range minimum queries (RMQ), where preprocessing an array into a Cartesian tree allows finding the minimum value in any subarray in constant time after preprocessing, by reducing the query to finding the in the tree. It also underpins treaps, randomized binary search trees that achieve expected O(log n) time for insertions, deletions, and searches by assigning random priorities to keys, ensuring balanced height with high probability. Additionally, Cartesian trees facilitate parallel algorithms for problems like all-nearest-smaller-values and have implications for parallel sorting, and they appear in string algorithms for .

Fundamentals

Definition

A Cartesian tree is a binary tree derived from a sequence of numbers, where each node in the tree corresponds to an element in the sequence, satisfying both a binary search tree (BST) property with respect to the positions in the sequence and a min-heap property with respect to the values. Formally, given a sequence A = (a_1, a_2, \dots, a_n) of n numbers, the Cartesian tree T is defined recursively as follows: the root of T is the element a_k with the minimum value in A (ties broken arbitrarily); the left subtree of T is the Cartesian tree on the prefix subsequence (a_1, \dots, a_{k-1}); and the right subtree is the Cartesian tree on the suffix subsequence (a_{k+1}, \dots, a_n). When the sequence contains duplicate values, multiple valid Cartesian trees may exist due to ties in the minimum selection. To ensure a unique structure, ties are typically broken using a stable rule, such as selecting the leftmost occurrence of the minimum value, or by incorporating secondary keys like positions (e.g., treating each element as a pair (a_i, i) and minimizing first by a_i then by i). Alternatively, in randomized variants akin to , unique random priorities can replace or augment the values to resolve ties probabilistically. The resulting tree structure maintains that its in-order traversal exactly reproduces the original sequence A, reflecting the BST property on the implicit position coordinates (where positions $1 to n serve as increasing keys). Additionally, it satisfies the min-heap property, where each node's value is no greater than its children's values. The name "Cartesian tree" originates from its construction on points in the plane formed by the of position indices and sequence values—specifically, points (i, a_i) for i = 1 to n, with the tree built by recursively selecting the point with minimum y-coordinate (value a_i) as the , and partitioning the left and right subtrees based on the x-coordinate (position i). For example, consider the sequence [3, 1, 4, 2], corresponding to points (1,3), (2,1), (3,4), (4,2). The minimum value is 1 at position 2, so it becomes the root. The left subsequence {{grok:render&&&type=render_inline_citation&&&citation_id=3&&&citation_type=wikipedia}} forms a left child node with value 3. The right subsequence [4, 2] has minimum 2 at position 4, so a right child node with value 2, whose left child is 4. The tree satisfies the in-order traversal $3, 1, 4, 2 and the min-heap property (1 < 3, 1 < 2, 2 < 4). This structure can be visualized as: 
    1
   / \
  3   2
     /
    4

Properties

The combines the properties of a and a (). It satisfies the heap-ordering property with respect to the values (priorities) of the nodes and the BST-ordering property with respect to their positions in the original sequence. In the standard variant, every node has a value smaller than or equal to the values of all its descendants, ensuring that the root holds the minimum value in the sequence. This can be formally expressed as: for any node v with value y_v, and for all descendants d of v, y_d \geq y_v. A variant reverses this ordering, with each node larger than its descendants. These heap properties hold recursively across the left and right subtrees. The in-order traversal of a Cartesian tree yields the nodes in the exact order of the original input sequence. This invariant arises directly from the BST structure imposed on the positions. Treating the positions (or indices) in the sequence as keys, the tree adheres to the BST property: for any node, all positions in its left subtree are less than the node's position, and all in its right subtree are greater. This positional ordering complements the value-based heap property, enabling efficient range-based operations. For a sequence with distinct values and a fixed tie-breaking rule (e.g., based on position for equal values), there exists exactly one Cartesian tree. This uniqueness follows from the deterministic recursive construction process. The height of a Cartesian tree is O(n) in the worst case, such as when the sequence is monotonically increasing or decreasing, resulting in a degenerate linear structure. However, when priorities (values) are assigned randomly—equivalent to a —the expected height is O(\log n), providing balanced performance with high probability.

Historical Development

Origins

The Cartesian tree was invented by Jean Vuillemin in 1980. It was introduced in his paper "A Unifying Look at Data Structures," published in Communications of the ACM. Vuillemin defined the Cartesian tree as a binary tree that simultaneously satisfies the properties of a on sequence positions and a on associated values. The original context for the Cartesian tree arose from challenges in computational geometry during the late 1970s and early 1980s, where efficient data structures were needed to handle searching and manipulation in multidimensional spaces. Vuillemin conceptualized sequences of values as sets of points in the plane, with x-coordinates representing the positions in the sequence and y-coordinates denoting the priorities or values at those positions. This geometric pairing enabled the tree to support operations like associative searching by combining inorder traversal for positional ordering with min-heap (or max-heap) ordering for priorities, thus facilitating efficient nearest neighbor and range-based queries on the point set. The naming of the structure as a "Cartesian tree" directly stems from its reliance on Cartesian coordinates to pair sequence positions with values, emphasizing the two-dimensional geometric foundation. Early applications focused primarily on , particularly , where the tree allowed for the decomposition of query regions into subtrees for rapid reporting or counting of points within specified bounds. This approach provided a unifying framework for problems in list manipulation and geometric searching, demonstrating practical efficiency in average-case performance for dynamic data scenarios.

Key Developments

Following the initial conceptualization for geometric range searching, Cartesian trees saw significant theoretical expansion in the 1990s through their connection to randomized binary search trees. In 1996, Seidel and Aragon introduced treaps, which are Cartesian trees where node priorities are randomly assigned real numbers, ensuring expected O(log n) time for insertions, deletions, and searches in a balanced structure. This linkage demonstrated how Cartesian trees could underpin probabilistic balancing in search trees, bridging geometric origins with probabilistic data structures. A major advancement in succinct data structures occurred in 2000, when Bender and Farach-Colton leveraged to solve the lowest common ancestor (LCA) problem in constant time. Their approach represents trees using O(n) bits via the Cartesian tree of Euler tour depths, enabling O(1)-time LCA queries after linear preprocessing, which was pivotal for space-efficient representations of static trees. This work highlighted the utility of in reducing space complexity for fundamental tree operations without sacrificing query speed. In the 2010s, Cartesian trees were integrated into advanced pattern matching frameworks, particularly through representations of longest common prefixes in generalized suffix trees. Navarro's contributions in compact data structures utilized Cartesian trees to encode LCP arrays efficiently, supporting operations like pattern searching in compressed suffix trees with near-optimal space and time bounds. This expansion extended Cartesian trees from static sequences to complex string processing, enabling scalable indexing for multiple texts. Recent developments up to 2025 have focused on parallel and dynamic extensions. In 2014, Blelloch and Shun presented a parallel algorithm for constructing multiway in O(log n) time with linear work, applicable to parallel building, addressing scalability for large datasets. In the 2020s, advancements in matching have enabled efficient algorithms for approximate pattern matching under edit distances, with applications in .

Construction Methods

Static Construction

Static construction of a Cartesian tree from a fixed sequence of n elements can be performed in linear time using several algorithms, each achieving O(n) time and O(n) space complexity. These methods are particularly efficient for one-time building scenarios, avoiding the overhead of dynamic updates. The resulting tree satisfies the min-heap property (or max-heap, depending on the variant) and the inorder traversal reproduces the input sequence. One widely used approach is the stack-based algorithm, which processes the sequence from left to right while maintaining a representing the right spine of the current tree. For each new element, nodes are popped from the stack until the top element is smaller than the new one (or the stack is empty), with the last popped node becoming the left child of the new element. The new element is then attached as the right child of the new stack top (or as the root if empty), and pushed onto the stack. This ensures the heap property is maintained, as each node is pushed and popped at most once, yielding O(n) total operations. The following pseudocode illustrates the stack-based construction for a min-Cartesian tree (assuming 0-based indexing and a sequence A[0..n-1]): 
function buildCartesianTree(A):
    n = length(A)
    tree = array of nodes with values A[i] and indices i
    stack = empty stack of indices
    for i from 0 to n-1:
        last = null
        while stack not empty and A[stack.top()] > A[i]:
            last = stack.pop()
        tree[i].left = last
        if stack not empty:
            tree[stack.top()].right = i
        else:
            root = i
        stack.push(i)
    return root  // index of the root node
This algorithm handles ties by treating equal values as greater than the current (or vice versa, depending on the convention), ensuring consistency with the Cartesian tree definition's priority rules for duplicate minima. An alternative method precomputes the all-nearest-smaller-values (ANSV) for each element, identifying the closest smaller element to the left and right. The parent of each node is then set to its nearest smaller neighbor in either direction, forming the tree by linking these pointers. The ANSV can itself be computed in O(n) time using a monotonic stack, similar to the main construction. This approach directly encodes the tree structure via parent relations and is useful when nearest smaller queries are needed independently. A divide-and-conquer recursively builds Cartesian trees for the left and right halves of the sequence, then merges them by comparing the roots and attaching the of the larger-root subtree to the smaller-root one. Specifically, the right of the left subtree is merged with the left of the right subtree by traversing and rewiring based on values, protecting nodes once merged to avoid reprocessing. The merge step processes only the spines, which amortize to O(1) per node across recursions, ensuring overall O(n) work and space. This method naturally extends to parallel settings with polylogarithmic depth.

Dynamic Construction

Dynamic construction of Cartesian trees enables maintenance of the structure over evolving sequences subject to insertions and deletions, ensuring efficient updates while preserving the and min- (or max-) properties. Dynamic Cartesian trees are closely related to implicit , where positions are handled implicitly using subtree sizes rather than explicit keys. One standard approach for insertion at a specific position k treats the tree as an implicit with values as priorities: the tree is split into left (first k-1 elements) and right (remaining) subtrees in amortized O(log n) time, the new node is created, and the three parts are merged while performing rotations to restore the . This process takes amortized O(log n) time per operation. If the values are randomly ordered, the expected height is O(log n), yielding expected O(log n) time; for arbitrary values, ensures O(log n) time. For deletion, the target node (located by position via sizes in O(log n) amortized time) is removed by merging its left and right subtrees after rotating it down—swapping with the higher-priority child (lower value in min-heap)—until it is a leaf; this also achieves amortized O(log n) time. To handle deletions more efficiently in practice, especially for weak or lazy deletions where elements are marked but not immediately removed from the sequence, nodes are flagged as deleted without restructuring, and subtrees are rebuilt only upon access or when a constant fraction of nodes are marked, yielding amortized O(log n) time per operation through periodic global rebuilds costing O(n). Full rebuild variants extend this by performing O(n)-time reconstructions after batches of updates, amortizing to O(log n) per operation over many changes, or integrating with advanced dynamic tree frameworks like link-cut trees to support link and cut operations in O(log n) worst-case time, enabling fully dynamic maintenance without amortization reliance. Recent advances in 2025 introduce parallel dynamic updates via multi-threaded spine merging techniques, adapted for batch insertions and deletions in clustering contexts, achieving O(log n) amortized work per operation with O(log n log k) span for k updates, though degenerating to O(n) worst-case without randomization.

Applications

Range Queries and Lowest Common Ancestors

Cartesian trees provide an efficient framework for solving range minimum queries (RMQ) on static arrays by reducing the problem to finding the lowest common ancestor (LCA) in the tree structure. For an array A of n elements, the Cartesian tree is constructed such that the in-order traversal matches the array positions, and the tree satisfies the min-heap property on values. A range minimum query RMQ(i, j) identifies the minimum value in A[i..j] by computing the LCA of the nodes corresponding to positions i and j in the Euler tour representation of the tree; this LCA node holds the position and value of the minimum element in the range. Consider the array [3, 1, 4, 2]. The Cartesian tree has root at position 2 (value 1), with left child at position 1 (value 3) and right subtree rooted at position 4 (value 2) with left child at position 3 (value 4). For RMQ on indices [1,4], the LCA of nodes at positions 1 and 4 is the root (position 2, value 1), correctly identifying the range minimum. To achieve constant-time queries, the Cartesian tree enables LCA preprocessing in O(n) time and space, with subsequent LCA queries (and thus RMQ) answered in O(1) time using methods like the RMQ-to-LCA conversion via Euler tour and depth arrays, or the Farach-Colton algorithm that normalizes blocks for table lookups. Originally introduced for 2D , Cartesian trees support orthogonal queries on point sets by structuring points as trees where x-coordinates follow order and y-coordinates satisfy min-heap order, enabling efficient splitting (CUT) and merging (CONCATENATE) operations to isolate points in rectangular ranges with average O(\log n) comparisons per operation. In the context of ultrametric distances, a Cartesian tree induces an ultrametric on its leaves by defining the distance between two leaves as the of their LCA, which corresponds to the minimum weight on the between them when tree edges represent distances; queries for path minima can thus be resolved via LCA computations in the .

Binary Search Trees

A treap is a randomized binary search tree that leverages the Cartesian tree structure by assigning each node a key from the ordered set and an independent random priority drawn uniformly from a continuous distribution, such as the unit interval [0, 1]. The resulting tree satisfies the (BST) property—in which an in-order traversal yields the keys in sorted order—with respect to the keys and the min- property with respect to the priorities p_i, where the root has the minimum priority and subtrees recursively satisfy the same. This dual satisfaction ensures that the treap corresponds exactly to a Cartesian tree on the defined by the keys, with heap ordering imposed by the random priorities rather than sequence minima. The random priorities p_i guarantee probabilistic balance: the expected height of the treap is O(\log n), and the probability that the height exceeds c \log n (for constant c > 2) is exponentially small, at most n^{-\Omega(c)}. Search operations follow the standard BST traversal using keys, taking expected O(\log n) time due to the balanced height. Insertion begins with a BST insertion of the new node (with its randomly chosen priority), followed by a series of parent-child rotations to restore the min-heap property on priorities, analogous to sifting up in a heap; this also runs in expected O(\log n) time. Deletion similarly rotates the target node down to a leaf (sifting down) before removal, again in expected O(\log n) time. Compared to deterministic balanced BSTs like AVL or red-black trees, treaps offer simpler implementations, as they rely solely on random priorities for without needing intricate rotation invariants or color rules beyond heap maintenance. Zip trees provide a simplified variant of this approach, maintaining the Cartesian tree foundation but using integer ranks drawn from a —specifically, \Pr[\text{rank} = k] = 2^{-(k+1)} for k \geq 0—to order nodes in a max-, with ties broken by smaller keys. This distribution ensures an expected rank of 1 and allows efficient "unzip" operations that decompose path into left and right chains during insertion, reattaching them as subtrees of the new node, and "" operations that merge chains during deletion, avoiding explicit rotations entirely. Zip trees inherit strong balance guarantees, with expected depth O(\log n) and the probability of any node's depth exceeding c \log n at most $1/n^c for c \geq 1, while requiring only O(\log \log n) random bits per node compared to treaps.

Sorting

The Levcopoulos–Petersson algorithm, developed in the late , employs to enable efficient of sequences that exhibit partial order, particularly those with a limited number of monotonic runs. The process begins by constructing a Cartesian tree from the input in linear time, treating the tree as a min-heap ordered by element values and a ordered by their positions in the sequence. proceeds via a heap-like : a is initialized with the tree's root, which holds the global minimum. The minimum is output by popping the queue's head, after which the node's left and right children (roots of subtrees representing contiguous input segments) are inserted into the queue. This continues until the queue empties, yielding the sorted sequence. The tree's structure inherently captures runs as subtrees, facilitating a bottom-up merge of these ordered segments during traversal. This approach achieves a time complexity of O(n \log \mathrm{Osc}), where \mathrm{Osc} denotes the number of oscillations—a presortedness measure equal to the minimum number of monotone subsequences required to cover the input minus one. For an input divided into k increasing runs, \mathrm{Osc} = k - 1, reducing the complexity to O(n \log k). When k \ll n, as in nearly sorted data, this outperforms general comparison-based sorts bounded by O(n \log n), providing optimality for such cases by minimizing comparisons and operations proportional to disorder. A variant achieves O(n + k \log k) time by selecting and sorting the k run minima explicitly before merging, leveraging linear-time selection. The Cartesian tree's height and balance reflect the input's disorder, with low \mathrm{Osc} yielding a structure where long chains represent runs and cross-run connections are sparse, enabling efficient operations during merging. For instance, in a sequence of k increasing runs, the tree's subtrees align with these runs, allowing traversal to merge them in a manner akin to , where piles (or runs) are combined based on their minima without full resorting of ordered portions. This integration of tree-based run detection with extraction ensures that presorted elements incur minimal cost, as subtrees for intact runs are processed in constant time per element.

Pattern Matching

Cartesian trees find significant application in string pattern matching, particularly through structural comparisons that leverage the tree's ability to encode relative minima and sequence order. One key use is in representing strings within generalized suffix trees, where the longest common prefix (LCP) array of a generalized suffix array is transformed into a to facilitate efficient construction. This approach allows for the O(n) time building of the for multiple strings, as the on the directly captures the branching structure needed to merge suffixes without redundant computations. In subsequence and substring matching, Cartesian trees enable isomorphism tests to detect pattern occurrences in a text by comparing tree structures rather than exact character sequences. Two strings are said to Cartesian-tree match if their Cartesian trees are isomorphic as ordered trees, preserving the relative positions of minima. This structural matching identifies substrings or subsequences in the text that exhibit the same hierarchical minimum pattern as the query, useful for detecting motifs in genomic or textual data where exact matches are too restrictive. For instance, in the text "banana", the pattern "ana" (positions 2–4) forms a Cartesian tree with the first 'a' as root (minimum), 'n' as right child, and the second 'a' as right grandchild; an isomorphism test on the text's potential substrings quickly verifies occurrences at positions 4–6 as well. Efficient algorithms for this matching draw from classical string techniques adapted to tree structures. A linear-time solution based on the Knuth-Morris-Pratt (KMP) algorithm performs single-pattern Cartesian tree matching by encoding the tree as a of left-to-right minima traversals, allowing shifts and comparisons akin to KMP's failure function. In the , variants incorporating Z-algorithm principles extended this to multiple patterns and longest common subsequences under Cartesian-tree matching, achieving quadratic time for computation while enabling efficient reporting of all matching positions. These methods, refined by and collaborators in compressed indexing contexts, support O(n) preprocessing for a text of length n, followed by O(m + occ) query time for a pattern of length m and occ occurrences. Recent extensions apply Cartesian trees to compressed representations, including integration with the Burrows-Wheeler transform (BWT) for pattern matching on circular or repetitive texts. By extending the BWT to encode Cartesian tree structures, indexes can report matching substrings in compressed space (O(n log σ) bits, where σ is the alphabet size) with near-linear query times, suitable for large-scale bioinformatics applications up to 2025. This builds on earlier compact indexes for exact Cartesian tree matching, enhancing scalability for compressed texts without decompressing the entire input.