PK

PKBytes

Explore tracks
Chapter 30: Static Range Queries and Decomposition Techniques
30.04Intermediate / Advanced4 topics13 min4 interactive animations

Cartesian tree

A Cartesian tree arranges an array as a heap-ordered binary tree whose in-order reading is the array itself, so range minimum queries become lowest-common-ancestor queries.

Learning goals

  • Define a Cartesian tree and state its two properties
  • Build one in O(n) with a monotonic stack
  • Reduce a range minimum query to finding a node in the tree
  • Explain the link between RMQ and the lowest common ancestor

Prerequisites

Binary treesMonotonic stackSparse table

A heap tells you the minimum, an array tells you the order. A Cartesian tree keeps both: the minimum is at the top, and reading the tree from left to right gives back the array.

30.04.1

RMQ reduction

In a min-heap-ordered Cartesian tree, the minimum of a[l..r] sits at the lowest common ancestor of the nodes l and r. To find it, start at the root and go down: if the current index is below l, every index in the range is in its right subtree; if it is above r, they are in its left subtree; the first index inside [l, r] is the answer.

Run the preset "Range minimum" (9 3 7 1 8 12 10 20, range [4, 7]): the animation walks down from the root (index 3, value 1), goes right once, and stops at index 4 with value 8. The walk is O(height) in the worst case, but the connection to O(1) queries is that the LCA problem has constant-time solutions.

Java
1class CartesianRmq {
2    private final int[] left, right;
3    private final int root;
4    CartesianRmq(int[] a) {
5        int n = a.length;
6        left = new int[n]; right = new int[n];
7        Arrays.fill(left, -1); Arrays.fill(right, -1);
8        int[] stack = new int[n];
9        int top = 0;
10        for (int i = 0; i < n; i++) {
11            int last = -1;
12            while (top > 0 && a[stack[top - 1]] > a[i]) last = stack[--top];
13            left[i] = last;
14            if (top > 0) right[stack[top - 1]] = i;
15            stack[top++] = i;
16        }
17        root = stack[0];
18    }
19    int argMin(int l, int r) {                   // index of the leftmost minimum in [l, r]
20        int v = root;
21        while (v < l || v > r) v = v < l ? right[v] : left[v];
22        return v;
23    }
24}

Cartesian tree: monotonic-stack build and range minimum as an LCA

Interactive · edit the input

Your input

Try

a[]

90
31
72
13
84
125
106
207

stack (indices, bottom to top)

empty
Setup

A Cartesian tree has the minimum at the root, the part left of it as the left subtree and the part right of it as the right subtree, recursively. The array order is the in-order order. A stack holds the right spine, whose values increase from the root down.

Step 1 / 14
Java
1int[] left, right;                               // child indices, -1 for none
2int build(int[] a) {                             // min-heap Cartesian tree; returns the root
3    int n = a.length; left = new int[n]; right = new int[n];
4    Arrays.fill(left, -1); Arrays.fill(right, -1);
5    int[] stack = new int[n]; int top = 0;
6    for (int i = 0; i < n; i++) {
7        int last = -1;
8        while (top > 0 && a[stack[top - 1]] > a[i]) last = stack[--top];    // larger values go below i, on its left
9        left[i] = last;
10        if (top > 0) right[stack[top - 1]] = i;                             // i hangs under the smaller value, on the right
11        stack[top++] = i;
12    }
13    return stack[0];
14}
15int rmq(int root, int l, int r) {                // index of the minimum in [l, r]
16    int v = root;                                // the first node on the way down whose index lies in [l, r]
17    while (v < l || v > r) v = v < l ? right[v] : left[v];
18    return v;
19}

Live state

0 pops

n

8

No condition evaluated on this step
Execution trace (dry run table)Show 14 steps
StepLineStateWhat happens
1L5n=8A Cartesian tree has the minimum at the root, the part left of it as the left subtree and the part right of it as the right subtree, recursively. The array order is the in-order order. A stack holds the right spine, whose values increase from the root down.
2L11i=0 value=9 left=none parent=noneInsert index 0 (9): its left child is empty, and it is the new root.
3L8i=1 value=3 popped=09 (index 0) is larger than 3: pop it. It and everything popped before it will form the left subtree of index 1.
4L11i=1 value=3 left=0 parent=noneInsert index 1 (3): its left child is index 0, and it is the new root.
5L11i=2 value=7 left=none parent=1Insert index 2 (7): its left child is empty, and it becomes the right child of index 1 (3).
6L8i=3 value=1 popped=27 (index 2) is larger than 1: pop it. It and everything popped before it will form the left subtree of index 3.
7L8i=3 value=1 popped=13 (index 1) is larger than 1: pop it. It and everything popped before it will form the left subtree of index 3.
8L11i=3 value=1 left=1 parent=noneInsert index 3 (1): its left child is index 1, and it is the new root.
9L11i=4 value=8 left=none parent=3Insert index 4 (8): its left child is empty, and it becomes the right child of index 3 (1).
10L11i=5 value=12 left=none parent=4Insert index 5 (12): its left child is empty, and it becomes the right child of index 4 (8).
11L8i=6 value=10 popped=512 (index 5) is larger than 10: pop it. It and everything popped before it will form the left subtree of index 6.
12L11i=6 value=10 left=5 parent=4Insert index 6 (10): its left child is index 5, and it becomes the right child of index 4 (8).
13L11i=7 value=20 left=none parent=6Insert index 7 (20): its left child is empty, and it becomes the right child of index 6 (10).
14L13return=3 pops=4The root is index 3 (value 1). Each index is pushed once and popped at most once, so the build is O(n) for 4 pops.
30.04.2

Monotonic stack construction

Build the tree left to right with a stack holding the **right spine**: the path from the root going right, whose values increase from top of tree to bottom. For each new value, pop every larger value off the stack; the last popped one becomes the new node's left child. Then the new node becomes the right child of the value now on top, and is pushed.

Each index is pushed once and popped at most once, so the build is O(n). The preset "Build" with 9 3 7 1 8 12 10 20 makes 4 pops; "Sorted input: a long right spine" makes none, because every value is larger than the previous one and simply extends the spine. The code returns a parent array instead of child arrays, which is often all that is needed.

Java
1static int[] parentArray(int[] a) {              // parent[i] = index of i's parent in the min Cartesian tree, -1 for the root
2    int n = a.length;
3    int[] parent = new int[n];
4    Arrays.fill(parent, -1);
5    int[] stack = new int[n];
6    int top = 0;
7    for (int i = 0; i < n; i++) {
8        int last = -1;
9        while (top > 0 && a[stack[top - 1]] > a[i]) last = stack[--top];
10        if (last >= 0) parent[last] = i;         // the popped chain hangs under i on its left
11        if (top > 0) parent[i] = stack[top - 1]; // and i hangs under the smaller value on the right
12        stack[top++] = i;
13    }
14    return parent;
15}

Cartesian tree: monotonic-stack build and range minimum as an LCA

Interactive · edit the input

Your input

Try

a[]

90
31
72
13
84
125
106
207

stack (indices, bottom to top)

empty
Setup

A Cartesian tree has the minimum at the root, the part left of it as the left subtree and the part right of it as the right subtree, recursively. The array order is the in-order order. A stack holds the right spine, whose values increase from the root down.

Step 1 / 14
Java
1int[] left, right;                               // child indices, -1 for none
2int build(int[] a) {                             // min-heap Cartesian tree; returns the root
3    int n = a.length; left = new int[n]; right = new int[n];
4    Arrays.fill(left, -1); Arrays.fill(right, -1);
5    int[] stack = new int[n]; int top = 0;
6    for (int i = 0; i < n; i++) {
7        int last = -1;
8        while (top > 0 && a[stack[top - 1]] > a[i]) last = stack[--top];    // larger values go below i, on its left
9        left[i] = last;
10        if (top > 0) right[stack[top - 1]] = i;                             // i hangs under the smaller value, on the right
11        stack[top++] = i;
12    }
13    return stack[0];
14}
15int rmq(int root, int l, int r) {                // index of the minimum in [l, r]
16    int v = root;                                // the first node on the way down whose index lies in [l, r]
17    while (v < l || v > r) v = v < l ? right[v] : left[v];
18    return v;
19}

Live state

0 pops

n

8

No condition evaluated on this step
Execution trace (dry run table)Show 14 steps
StepLineStateWhat happens
1L5n=8A Cartesian tree has the minimum at the root, the part left of it as the left subtree and the part right of it as the right subtree, recursively. The array order is the in-order order. A stack holds the right spine, whose values increase from the root down.
2L11i=0 value=9 left=none parent=noneInsert index 0 (9): its left child is empty, and it is the new root.
3L8i=1 value=3 popped=09 (index 0) is larger than 3: pop it. It and everything popped before it will form the left subtree of index 1.
4L11i=1 value=3 left=0 parent=noneInsert index 1 (3): its left child is index 0, and it is the new root.
5L11i=2 value=7 left=none parent=1Insert index 2 (7): its left child is empty, and it becomes the right child of index 1 (3).
6L8i=3 value=1 popped=27 (index 2) is larger than 1: pop it. It and everything popped before it will form the left subtree of index 3.
7L8i=3 value=1 popped=13 (index 1) is larger than 1: pop it. It and everything popped before it will form the left subtree of index 3.
8L11i=3 value=1 left=1 parent=noneInsert index 3 (1): its left child is index 1, and it is the new root.
9L11i=4 value=8 left=none parent=3Insert index 4 (8): its left child is empty, and it becomes the right child of index 3 (1).
10L11i=5 value=12 left=none parent=4Insert index 5 (12): its left child is empty, and it becomes the right child of index 4 (8).
11L8i=6 value=10 popped=512 (index 5) is larger than 10: pop it. It and everything popped before it will form the left subtree of index 6.
12L11i=6 value=10 left=5 parent=4Insert index 6 (10): its left child is index 5, and it becomes the right child of index 4 (8).
13L11i=7 value=20 left=none parent=6Insert index 7 (20): its left child is empty, and it becomes the right child of index 6 (10).
14L13return=3 pops=4The root is index 3 (value 1). Each index is pushed once and popped at most once, so the build is O(n) for 4 pops.
30.04.3

Cartesian tree properties

A Cartesian tree of an array has two properties. **Heap order**: every node is at most (for a min tree) its children. **In-order**: reading the tree in-order gives the indices 0, 1, 2, ..., n - 1, so the tree is a binary tree over the positions, not over the values. Together they determine the tree uniquely when values are distinct; with equal values a tie rule decides, and the stack code above keeps the earlier equal value above the later one.

More properties follow: the root is the (leftmost) minimum; the left subtree is the Cartesian tree of the part left of it and the right subtree that of the part right of it; the height equals the longest chain of nested minima. The preset "Repeated minimum" (5 2 7 2 9 2) shows the tie rule: the root is the first 2, at index 1, and the other 2s are on its right spine.

Java
1static boolean isCartesianTree(int[] a, int[] left, int[] right, int root) {
2    int n = a.length;
3    List<Integer> order = new ArrayList<>();
4    if (!inorder(root, left, right, a, order, n)) return false;
5    for (int i = 0; i < n; i++) if (order.size() != n || order.get(i) != i) return false;   // in-order must be 0..n-1
6    return true;
7}
8private static boolean inorder(int v, int[] left, int[] right, int[] a, List<Integer> out, int n) {
9    if (v == -1) return true;
10    if (out.size() > n) return false;            // guards against cycles
11    if (left[v] != -1 && a[left[v]] < a[v]) return false;   // heap order
12    if (right[v] != -1 && a[right[v]] < a[v]) return false;
13    return inorder(left[v], left, right, a, out, n) && add(out, v) && inorder(right[v], left, right, a, out, n);
14}
15private static boolean add(List<Integer> out, int v) { out.add(v); return true; }

Cartesian tree: monotonic-stack build and range minimum as an LCA

Interactive · edit the input

Your input

Try

a[]

90
31
72
13
84
125
106
207

stack (indices, bottom to top)

empty
Setup

A Cartesian tree has the minimum at the root, the part left of it as the left subtree and the part right of it as the right subtree, recursively. The array order is the in-order order. A stack holds the right spine, whose values increase from the root down.

Step 1 / 14
Java
1int[] left, right;                               // child indices, -1 for none
2int build(int[] a) {                             // min-heap Cartesian tree; returns the root
3    int n = a.length; left = new int[n]; right = new int[n];
4    Arrays.fill(left, -1); Arrays.fill(right, -1);
5    int[] stack = new int[n]; int top = 0;
6    for (int i = 0; i < n; i++) {
7        int last = -1;
8        while (top > 0 && a[stack[top - 1]] > a[i]) last = stack[--top];    // larger values go below i, on its left
9        left[i] = last;
10        if (top > 0) right[stack[top - 1]] = i;                             // i hangs under the smaller value, on the right
11        stack[top++] = i;
12    }
13    return stack[0];
14}
15int rmq(int root, int l, int r) {                // index of the minimum in [l, r]
16    int v = root;                                // the first node on the way down whose index lies in [l, r]
17    while (v < l || v > r) v = v < l ? right[v] : left[v];
18    return v;
19}

Live state

0 pops

n

8

No condition evaluated on this step
Execution trace (dry run table)Show 14 steps
StepLineStateWhat happens
1L5n=8A Cartesian tree has the minimum at the root, the part left of it as the left subtree and the part right of it as the right subtree, recursively. The array order is the in-order order. A stack holds the right spine, whose values increase from the root down.
2L11i=0 value=9 left=none parent=noneInsert index 0 (9): its left child is empty, and it is the new root.
3L8i=1 value=3 popped=09 (index 0) is larger than 3: pop it. It and everything popped before it will form the left subtree of index 1.
4L11i=1 value=3 left=0 parent=noneInsert index 1 (3): its left child is index 0, and it is the new root.
5L11i=2 value=7 left=none parent=1Insert index 2 (7): its left child is empty, and it becomes the right child of index 1 (3).
6L8i=3 value=1 popped=27 (index 2) is larger than 1: pop it. It and everything popped before it will form the left subtree of index 3.
7L8i=3 value=1 popped=13 (index 1) is larger than 1: pop it. It and everything popped before it will form the left subtree of index 3.
8L11i=3 value=1 left=1 parent=noneInsert index 3 (1): its left child is index 1, and it is the new root.
9L11i=4 value=8 left=none parent=3Insert index 4 (8): its left child is empty, and it becomes the right child of index 3 (1).
10L11i=5 value=12 left=none parent=4Insert index 5 (12): its left child is empty, and it becomes the right child of index 4 (8).
11L8i=6 value=10 popped=512 (index 5) is larger than 10: pop it. It and everything popped before it will form the left subtree of index 6.
12L11i=6 value=10 left=5 parent=4Insert index 6 (10): its left child is index 5, and it becomes the right child of index 4 (8).
13L11i=7 value=20 left=none parent=6Insert index 7 (20): its left child is empty, and it becomes the right child of index 6 (10).
14L13return=3 pops=4The root is index 3 (value 1). Each index is pushed once and popped at most once, so the build is O(n) for 4 pops.
30.04.4

LCA connection

RMQ and the lowest common ancestor (LCA) are two views of one problem. RMQ on an array reduces to LCA in its Cartesian tree, as shown above. Conversely, LCA on any tree reduces to RMQ on the **Euler tour** depths: walk the tree, record the depth every time you enter a node or return to it, and note the first position of each node; the LCA of u and v is the node of minimum depth between their first positions.

Combining both with the sparse table gives an O(n log n) preprocessing and O(1) LCA queries. The class below does exactly that for a tree given by a parent array (with parent[i] < i), returning the lowest common ancestor by an O(1) argmin over the Euler tour.

Java
1class LcaEuler {
2    private final int[] euler, first, depth;
3    private final int[][] idx;                   // sparse table of Euler positions by depth
4    LcaEuler(int[] parent) {                     // parent[0] = -1 and parent[i] < i
5        int n = parent.length;
6        List<List<Integer>> kids = new ArrayList<>();
7        for (int i = 0; i < n; i++) kids.add(new ArrayList<>());
8        depth = new int[n];
9        for (int i = 1; i < n; i++) { kids.get(parent[i]).add(i); depth[i] = depth[parent[i]] + 1; }
10        List<Integer> tour = new ArrayList<>();
11        first = new int[n];
12        Deque<int[]> stack = new ArrayDeque<>();           // {node, next child position}
13        stack.push(new int[]{0, 0});
14        first[0] = 0;
15        tour.add(0);
16        while (!stack.isEmpty()) {
17            int[] top = stack.peek();
18            if (top[1] < kids.get(top[0]).size()) {
19                int c = kids.get(top[0]).get(top[1]++);
20                first[c] = tour.size();
21                tour.add(c);
22                stack.push(new int[]{c, 0});
23            } else {
24                stack.pop();
25                if (!stack.isEmpty()) tour.add(stack.peek()[0]);   // return to the parent
26            }
27        }
28        euler = tour.stream().mapToInt(Integer::intValue).toArray();
29        int m = euler.length, K = 32 - Integer.numberOfLeadingZeros(m);
30        idx = new int[K][];
31        idx[0] = new int[m];
32        for (int i = 0; i < m; i++) idx[0][i] = i;
33        for (int k = 1; k < K; k++) {
34            idx[k] = new int[m - (1 << k) + 1];
35            for (int i = 0; i + (1 << k) <= m; i++) {
36                int x = idx[k - 1][i], y = idx[k - 1][i + (1 << (k - 1))];
37                idx[k][i] = depth[euler[x]] <= depth[euler[y]] ? x : y;
38            }
39        }
40    }
41    int lca(int u, int v) {
42        int l = Math.min(first[u], first[v]), r = Math.max(first[u], first[v]);
43        int k = 31 - Integer.numberOfLeadingZeros(r - l + 1);
44        int x = idx[k][l], y = idx[k][r - (1 << k) + 1];
45        return euler[depth[euler[x]] <= depth[euler[y]] ? x : y];
46    }
47}

Cartesian tree: monotonic-stack build and range minimum as an LCA

Interactive · edit the input

Your input

Try

a[]

90
31
72
13
84
125
106
207

stack (indices, bottom to top)

empty
Setup

A Cartesian tree has the minimum at the root, the part left of it as the left subtree and the part right of it as the right subtree, recursively. The array order is the in-order order. A stack holds the right spine, whose values increase from the root down.

Step 1 / 14
Java
1int[] left, right;                               // child indices, -1 for none
2int build(int[] a) {                             // min-heap Cartesian tree; returns the root
3    int n = a.length; left = new int[n]; right = new int[n];
4    Arrays.fill(left, -1); Arrays.fill(right, -1);
5    int[] stack = new int[n]; int top = 0;
6    for (int i = 0; i < n; i++) {
7        int last = -1;
8        while (top > 0 && a[stack[top - 1]] > a[i]) last = stack[--top];    // larger values go below i, on its left
9        left[i] = last;
10        if (top > 0) right[stack[top - 1]] = i;                             // i hangs under the smaller value, on the right
11        stack[top++] = i;
12    }
13    return stack[0];
14}
15int rmq(int root, int l, int r) {                // index of the minimum in [l, r]
16    int v = root;                                // the first node on the way down whose index lies in [l, r]
17    while (v < l || v > r) v = v < l ? right[v] : left[v];
18    return v;
19}

Live state

0 pops

n

8

No condition evaluated on this step
Execution trace (dry run table)Show 14 steps
StepLineStateWhat happens
1L5n=8A Cartesian tree has the minimum at the root, the part left of it as the left subtree and the part right of it as the right subtree, recursively. The array order is the in-order order. A stack holds the right spine, whose values increase from the root down.
2L11i=0 value=9 left=none parent=noneInsert index 0 (9): its left child is empty, and it is the new root.
3L8i=1 value=3 popped=09 (index 0) is larger than 3: pop it. It and everything popped before it will form the left subtree of index 1.
4L11i=1 value=3 left=0 parent=noneInsert index 1 (3): its left child is index 0, and it is the new root.
5L11i=2 value=7 left=none parent=1Insert index 2 (7): its left child is empty, and it becomes the right child of index 1 (3).
6L8i=3 value=1 popped=27 (index 2) is larger than 1: pop it. It and everything popped before it will form the left subtree of index 3.
7L8i=3 value=1 popped=13 (index 1) is larger than 1: pop it. It and everything popped before it will form the left subtree of index 3.
8L11i=3 value=1 left=1 parent=noneInsert index 3 (1): its left child is index 1, and it is the new root.
9L11i=4 value=8 left=none parent=3Insert index 4 (8): its left child is empty, and it becomes the right child of index 3 (1).
10L11i=5 value=12 left=none parent=4Insert index 5 (12): its left child is empty, and it becomes the right child of index 4 (8).
11L8i=6 value=10 popped=512 (index 5) is larger than 10: pop it. It and everything popped before it will form the left subtree of index 6.
12L11i=6 value=10 left=5 parent=4Insert index 6 (10): its left child is index 5, and it becomes the right child of index 4 (8).
13L11i=7 value=20 left=none parent=6Insert index 7 (20): its left child is empty, and it becomes the right child of index 6 (10).
14L13return=3 pops=4The root is index 3 (value 1). Each index is pushed once and popped at most once, so the build is O(n) for 4 pops.

Practice ladder

Now try it yourself

Easy

  • Maximum Binary Tree

Medium

  • Maximum Binary Tree II
  • Lowest Common Ancestor of a Binary Tree

Advanced

  • Largest Rectangle in Histogram (Cartesian tree view)
  • Sum of Subarray Minimums
  • Company Queries II (CSES)

Key takeaways

  • A Cartesian tree is heap-ordered by value and in-order by index.
  • A monotonic stack builds it in O(n): pop larger values to form the left child, hang the node under the smaller value.
  • Range minimum = lowest common ancestor in the Cartesian tree; LCA = RMQ on the Euler tour depths.