The site's seventeenth node-linked trees entry, and a forward reference Treap's own "where treaps show up" section names without linking: "build a treap-shaped tree over an array where priority is the array value... that's exactly a Cartesian tree." A Cartesian tree is a Treap with the randomness removed — the same joint invariant (heap-ordered on one field, binary-search-tree-ordered on another) applied to a single array, where the "priority" that decides shape isn't a random number but the array's own values. Min-heap ordered on value and BST-ordered on index means the tree's in-order walk always recovers the array's original index order, no matter how the values are shuffled.
The payoff isn't sorting — it's a genuinely different way to answer "what's the smallest value between
index l and index r?" Sparse
Table and Segment Tree both answer that question
too, each precomputing combined values over sub-ranges directly. A Cartesian tree answers it a different
way entirely: build the tree once, and the lowest common ancestor of positions l and
r — a question about tree structure, nothing to do with ranges at all — turns out
to always be the position of the minimum value in [l, r].
The default array below is the same one Sparse Table's own worked example uses. Press Step or Run to watch the O(n) construction: one pass over the array, a stack of not-yet-finalized indices, popping anything the current element is smaller than and wiring up left/right children as it goes. Once the tree finishes building, click any two cells in the array to query a range: the path from each to their lowest common ancestor lights up, the LCA itself is marked, and the array's own range gets highlighted with the answer — checked live against a plain brute-force scan of that same range, which always agrees. Try the sorted (worst case) preset to see what happens to the tree's shape when the array has nothing to balance against.
Every node's subtree spans a contiguous block of original array indices — a direct consequence of BST-ordering on index — and the min-heap property means that node is always the smallest value anywhere in its own subtree. Put together: the root is the position of the array's global minimum, its left subtree is (recursively) the Cartesian tree of everything before that position, and its right subtree is the Cartesian tree of everything after it. That recursive split-at-the-minimum is exactly what the construction algorithm below carries out, one array element at a time.
The lowest common ancestor of positions l and r is the shallowest
node whose subtree contains both — equivalently, the node whose left/right children are the first place
the tree actually separates them. Walking the default array's tree: LCA(4, 6) asks for the
range [4, 6] = [9, 3, 7], minimum 3 at index 5. Index
4 sits at depth 2, index 6 at depth 3; lifting 6 up one level lands on index 7 (still not equal to 4), and
lifting both once more lands both on index 5 — their LCA, and exactly the range's minimum. This isn't a
coincidence for this one example: it holds because index 5's subtree is precisely the smallest node-range
containing both 4 and 6 (any node higher up would still be shallower but its subtree would extend further
than [4, 6] needed to), and by the recursive definition above, whatever node's subtree is
that range, that node is that range's minimum.
Construction matches the demo's stepper exactly: a single left-to-right pass with a stack of not-yet-finalized indices, popping anything bigger than the current element before pushing it. Query uses the simplest possible LCA — walk both nodes up to the root, recording depths, then climb the deeper one first and step both together once they match:
function buildCartesianTree(a) {
const n = a.length;
const left = new Array(n).fill(-1);
const right = new Array(n).fill(-1);
const parent = new Array(n).fill(-1);
const stack = []; // indices with no right child assigned yet, increasing value bottom-to-top
for (let i = 0; i < n; i++) {
let lastPopped = -1;
while (stack.length && a[stack[stack.length - 1]] > a[i]) {
lastPopped = stack.pop();
}
if (lastPopped !== -1) {
left[i] = lastPopped;
parent[lastPopped] = i;
}
if (stack.length) {
const top = stack[stack.length - 1];
right[top] = i;
parent[i] = top;
}
stack.push(i);
}
return { root: stack[0], left, right, parent };
}
function depthOf(parent, node) {
let d = 0, cur = node;
while (parent[cur] !== -1) { cur = parent[cur]; d++; }
return d;
}
function rangeMinIndex(tree, l, r) { // naive O(h) LCA — see Pitfalls for the O(log n) fix
let u = l, v = r;
let du = depthOf(tree.parent, u), dv = depthOf(tree.parent, v);
while (du > dv) { u = tree.parent[u]; du--; }
while (dv > du) { v = tree.parent[v]; dv--; }
while (u !== v) { u = tree.parent[u]; v = tree.parent[v]; }
return u;
}
const t = buildCartesianTree([5, 2, 8, 1, 9, 3, 7, 4]);
rangeMinIndex(t, 4, 6); // 5 — a[5] = 3, the minimum of a[4..6] = [9, 3, 7]A sorted array is the worst case, not a best case. With no value ever bigger than the one before it, the construction stack never pops — every new element becomes the right child of the previous one, and the tree degenerates into a single chain. Checked directly: the default 8-element array above builds a tree of height 3, but sorting those same 8 values ascending first produces a tree of height 7 — a straight line, the maximum possible for 8 nodes. This is the exact same shape pitfall Binary Search Tree's own Pitfalls section describes for sorted-input inserts, and it's why Treap exists — a treap dodges it by picking priorities at random instead of using the data itself. A Cartesian tree can't do that; the data is the priority, by definition. Try the sorted (worst case) preset above and watch the tree flatten into a chain.
The naive LCA above is O(h), not O(log n) — and h can be the full array length. On random data the tree's height stays close to logarithmic (measured directly: average height 12.4 for n=100, 21.1 for n=1,000, 30.6 for n=10,000, 38.2 for n=100,000 across dozens of random arrays each — roughly doubling n adds a small, shrinking amount to the height rather than doubling it), but on the sorted-array worst case above, every query degenerates to a full O(n) walk up the chain. Swapping in Binary Lifting's jump table over this same tree fixes that unconditionally, at the cost of an O(n log n) preprocessing pass instead of this page's O(n) one — worth it whenever the input can't be trusted to be well-shuffled.
Ties don't break the range-minimum answer, but they do decide the tree's exact shape.
The construction above pops only on strict >, so equal values never get reordered against
each other — the leftmost occurrence of a repeated minimum ends up as the higher ancestor, and later equal
occurrences hang off its right side. Checked against 20,000+ randomized trials including arrays with heavy
duplication: the LCA's value always matches an independent brute-force scan's minimum, even
though the LCA's specific index can differ from the brute-force scan's own tie-broken index when
more than one position shares the minimum value — both are equally valid range-minimum answers, since
range-minimum-query only promises a position holding the minimum value, not a specific one among ties.
Also worth being precise about, since Treap's own text already calls this "the standard O(n)-preprocessing, O(1)-query answer" — that full O(1) picture chains three separate pieces together: this page's O(n) tree construction, an Euler tour of the finished tree reduced to a restricted array where consecutive values only ever differ by exactly ±1, and an O(1)-query scheme built specifically for that restricted shape (a much easier problem than general range-minimum, solvable by block decomposition). This page builds and verifies the first piece and the LCA-equals-range-minimum property it depends on; the ±1-restricted-array trick that gets the query down to true O(1) is real and classic, but is its own separate structure this page doesn't build.
Time: O(n) to build — every index is pushed exactly once and popped at
most once, so the total work across the whole pass is linear despite the nested-looking
while. Query with the naive parent-walk LCA above is O(h), where h
is the tree's height: O(log n) on average for well-shuffled data (measured above), degrading
to O(n) on adversarial input like a sorted array (also measured above). Swapping in
Binary Lifting gets queries to a guaranteed
O(log n) regardless of input shape, at an O(n log n) preprocessing cost instead
of this page's O(n). Space: O(n) — one parent and up to two
child pointers per array element, no matter which query method sits on top.
This site's guide, Choosing a Search Tree, sets this entry aside from the seven it actually compares: it isn't about a set of keys at all — it's a Treap with the randomness removed, and its lowest common ancestor answers a stored array's range-minimum queries, a structural trick rather than a comparison-driven set operation.