Cartesian Tree

A Cartesian tree is a binary tree defined on a sequence of numbers where the root is the minimum value in the sequence, and subtrees represent subsequences divided by the root.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// Recursive construction 
Node construct(int[] arr, int low, int high) {
  if (low > high) return null;
  int min = findMin(arr, low, high);
  Node root = new Node(arr[min]);
  root.left = construct(arr, low, min-1);
  root.right = construct(arr, min+1, high);
  return root;
}

// Print inorder traversal
void printInOrder(Node root) {
  if (root == null) return;
  printInOrder(root.left);
  System.out.print(root.val + " ");
  printInOrder(root.right);  
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// Recursive construction
Node* construct(vector<int> arr, int low, int high) {
  if (low > high) return NULL;
  int min = findMin(arr, low, high);
  Node* root = new Node(arr[min]);
  root->left = construct(arr, low, min-1);
  root->right = construct(arr, min+1, high);
  return root;
}

// Print inorder 
void printInOrder(Node* root) {
  if (!root) return;
  printInOrder(root->left);
  cout << root->val << " ";
  printInOrder(root->right);
}

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

# Recursive construction  
def construct(arr, low, high):
  if low > high:
    return None
  min = find_min(arr, low, high)
  root = Node(arr[min])
  root.left = construct(arr, low, min-1)
  root.right = construct(arr, min+1, high)
  return root

# Print inorder
def print_inorder(root):
  if not root:
    return  
  print_inorder(root.left)
  print(root.val, end=' ')
  print_inorder(root.right)

Key properties:

  • Minimum element is root
  • Subarrays divided by root
  • Forms binary tree on sequence
  • Useful for range queries

The structure allows efficient range queries, making Cartesian trees a useful alternative to segment trees in some cases.

A Cartesian Tree is a binary tree derived from a sequence of numbers. It has two key properties:

  1. The tree is heap-ordered: each node is smaller (or larger) than its children, depending on whether it’s a min-heap or max-heap.
  2. An in-order traversal of the tree returns the original sequence.

The Cartesian tree is not necessarily balanced, but it’s often used in algorithms like RMQ (Range Minimum Query) because it can be constructed in linear time and takes linear space.

Example Code

Below are simplified examples to construct a Cartesian Tree for a given array of integers.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Node {
    int val;
    Node left, right;
    Node(int val) {
        this.val = val;
    }
}

public class CartesianTree {
    public static Node buildTree(int[] arr, int start, int end) {
        if (start > end) return null;

        int minIndex = start;
        for (int i = start; i <= end; i++) {
            if (arr[i] < arr[minIndex]) minIndex = i;
        }

        Node root = new Node(arr[minIndex]);
        root.left = buildTree(arr, start, minIndex - 1);
        root.right = buildTree(arr, minIndex + 1, end);

        return root;
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 6, 1, 9};
        Node root = buildTree(arr, 0, arr.length - 1);
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int val) : val(val), left(NULL), right(NULL) {}
};

Node* buildTree(int arr[], int start, int end) {
    if (start > end) return NULL;

    int minIndex = start;
    for (int i = start; i <= end; ++i) {
        if (arr[i] < arr[minIndex]) minIndex = i;
    }

    Node* root = new Node(arr[minIndex]);
    root->left = buildTree(arr, start, minIndex - 1);
    root->right = buildTree(arr, minIndex + 1, end);

    return root;
}

int main() {
    int arr[] = {3, 2, 6, 1, 9};
    Node* root = buildTree(arr, 0, 4);
    return 0;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def build_tree(arr, start, end):
    if start > end:
        return None

    min_index = start
    for i in range(start, end + 1):
        if arr[i] < arr[min_index]:
            min_index = i

    root = Node(arr[min_index])
    root.left = build_tree(arr, start, min_index - 1)
    root.right = build_tree(arr, min_index + 1, end)

    return root

if __name__ == "__main__":
    arr = [3, 2, 6, 1, 9]
    root = build_tree(arr, 0, len(arr) - 1)

These are basic examples to get you started with Cartesian Trees. They don’t include methods for tree traversal or additional utility functions.