Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 CartesianTree

Source Notebook

Generate a Cartesian tree for a given input list

Contributed by: Shenghui Yang

ResourceFunction["CartesianTree"][list]

generates the Cartesian tree for the numerical input list in min-heap.

ResourceFunction["CartesianTree"][list,type]

generates the Cartesian tree with specified type.

ResourceFunction["CartesianTree"][list,type,p]

generates the Cartesian tree with specified type and order function p.

Details

A Cartesian tree of a list is a binary tree constructed so that an in-order traversal of the tree returns the original list, while the tree also satisfies a heap property (either min-heap or max-heap) on the list values. The root is the minimum (or maximum) element of the list, and the left and right subtrees are recursively built from the sublists to the left and right of that element.
If no order function is specified, the input list must contain real values.
The type can be either min-heap (default) or max-heap. In a min-heap, the key at each node is less than or equal to the keys of its children, so the minimum element is always stored at the root. In contrast, a max-heap requires that the key at each node is greater than or equal to the keys of its children, placing the maximum element at the root.
The ordering function p can be NumericalOrder, AlphabeticOrder, LexicographicOrder and Order.
The ordering function p applies to a pair of elements following the description on the OrderedQ function page.
The function constructs a Cartesian tree by performing a depth-first search implemented via recursion, where the array is recursively partitioned around its extremal element. At each recursive call, the algorithm identifies the root of the current subtree, then descends into the left and right subarrays to build the corresponding child nodes.

Examples

Basic Examples (1) 

Create the Cartesian tree for the input list using min-heap:

In[1]:=
input = {9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5}; ResourceFunction["CartesianTree"][input]
Out[2]=

Scope (3) 

Create the Cartesian tree for the input list using max-heap:

In[3]:=
input = {9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5}; ResourceFunction["CartesianTree"][input, "MaxHeap"]
Out[4]=

CartesianTree works with DateObject:

In[5]:=
SeedRandom["Dates"]; dates = RandomDate[{DateObject[{2026, 1}, "Month"], DateObject[{2026, 12}, "Month"]}, 20, DateFormat -> {"Day", "/", "Month", "/", "Year"}]
Out[6]=
In[7]:=
ResourceFunction["CartesianTree"][dates, "MaxHeap", NumericalOrder]
Out[7]=

CartesianTree works with strings:

In[8]:=
SeedRandom["Words"]; w = RandomWord[20]
Out[9]=
In[10]:=
ResourceFunction["CartesianTree"][w, "MinHeap", LexicographicOrder]
Out[10]=

Properties and Relations (2) 

Recover the input list from the Cartesian tree using in-order scan:

In[11]:=
input = {9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5}; ct = ResourceFunction["CartesianTree"][input]
Out[12]=
In[13]:=
ds = CreateDataStructure["DynamicArray"];
In[14]:=
TreeScan[If[# =!= Null, ds["Append", #]] &, ct, TreeTraversalOrder -> "InOrder"]; ds["Elements"]
Out[15]=

The min and max heap trees may have different depth:

In[16]:=
input = {2, 100, 56, 40, 38, 62, 70, 82, 8, 57, 39, 22, 12, 88, 89, 7, 35, 20, 29, 17, 79, 80, 67, 69}; {ResourceFunction["CartesianTree"][input], ResourceFunction["CartesianTree"][input, "MaxHeap"]}
Out[17]=
In[18]:=
TreeDepth /@ %
Out[18]=

Possible Issues (3) 

If no order function is specified, the input list must contain real values:

In[19]:=
input = {9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5, "X"}; ResourceFunction["CartesianTree"][input, "MaxHeap"]
Out[20]=

The Cartesian tree function does not work properly with duplicated items:

In[21]:=
input = {9, 3, 4, 7, 1, 3, 8}; ResourceFunction["CartesianTree"][input, "MaxHeap"]
Out[22]=

Using DeleteDuplicates to clean the input before application:

In[23]:=
input = DeleteDuplicates@{9, 3, 4, 7, 1, 3, 8}; ResourceFunction["CartesianTree"][input, "MaxHeap"]
Out[24]=

The Cartesian tree can be very unbalanced:

In[25]:=
input = Sort@{9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5}; ResourceFunction["CartesianTree"][input, "MaxHeap"]
Out[26]=

Publisher

Shenghui Yang

Version History

  • 1.0.0 – 12 January 2026

Source Metadata

  • Citation:
    • Jean Vuillemin. 1980. A unifying look at data structures. Commun. ACM 23, 4 (April 1980), 229–239. https://dl.acm.org/doi/10.1145/358841.358852

Related Resources

License Information