Cartesian Tree
Build a tree whose inorder traversal is the array order and whose heap property exposes range minima or maxima.
Cartesian Tree
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
A Cartesian tree turns an array into a binary tree that preserves both index order and value order:
inorder traversal gives the original array order,
the tree satisfies a heap property on values.
That combination makes it useful whenever a range wants to split around its minimum or maximum element.
When to Use It
Use it when:
interval structure depends on the minimum or maximum element of the interval,
RMQ should become an LCA problem,
the statement hides recursive splits around dominant elements.
Core Idea
For a min Cartesian tree, the root of any subarray is its minimum element. The left child is built from the part to the left, and the right child from the part to the right. A monotonic stack builds the whole tree in linear time.
Key Insight
The tree stores the same information as repeated ``pick the minimum and recurse,'' but without paying \(O(n^2)\) for that recursion literally. The stack simulates how intervals nest around decreasing minima.
Worked Problem
Problem.
Given an array, repeatedly choose the minimum element of a segment as the segment's root and split left/right. Build the entire recursion tree.
Why Cartesian tree fits.
That recursion tree is the min Cartesian tree. The array index order becomes the inorder traversal, so subtree boundaries match contiguous ranges automatically.
Problem Pattern
This structure appears in:
RMQ to LCA reductions,
histogram problems,
divide-and-conquer recurrences that always pivot on the min or max element.
Correctness Intuition
The monotonic stack keeps the current right spine of the tree. When a smaller value arrives, larger values to its left can no longer stay above it in a min-heap tree, so they are popped and attached as its left child or as descendants on the correct side. The inorder order remains the original index order throughout.
Complexity Analysis
Building the tree takes \(O(n)\) time and \(O(n)\) memory.
Implementation
The code constructs the min Cartesian tree and returns:
the root index,
parent,
left child,
right child arrays.
Common Pitfalls
Mixing the min-tree and max-tree inequalities.
Ignoring equal values; the tie rule must be consistent.
Forgetting that the tree shape depends on whether ties favor earlier or later indices.
Variants / Extensions
Max Cartesian tree.
RMQ via Euler tour + LCA on the Cartesian tree.
Parsing interval DP recurrences through subtree structure.
Practice Problems
Build the Cartesian tree of an array.
Reduce RMQ to LCA.
Reconstruct recursion around interval minima or maxima.
References
Code
Contest-ready reference implementation for the idea explained above.
struct CartesianTree {
int root;
vector<int> parent;
vector<int> left_child;
vector<int> right_child;
};
CartesianTree build_min_cartesian_tree(const vector<int>& a) {
int n = (int)a.size();
vector<int> parent(n, -1), left_child(n, -1), right_child(n, -1);
vector<int> st;
for (int i = 0; i < n; ++i) {
int last = -1;
while (!st.empty() && a[i] < a[st.back()]) {
last = st.back();
st.pop_back();
}
if (!st.empty()) {
parent[i] = st.back();
right_child[st.back()] = i;
}
if (last != -1) {
parent[last] = i;
left_child[i] = last;
}
st.push_back(i);
}
int root = st.front();
while (parent[root] != -1) root = parent[root];
return {root, parent, left_child, right_child};
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.