What is a Cartesian Tree and What Is It Used For?
Learn what a Cartesian tree is, how it is built in O(n), and how it solves Range Minimum Query via LCA for this interview question.
Expected Interview Answer
A Cartesian tree is a binary tree built from a sequence of values where an in-order traversal recovers the original sequence order, and simultaneously the tree satisfies the min-heap (or max-heap) property with respect to the values, making the sequence's minimum sit at the root.
Given an array, the root is the position of the minimum element, and the left and right subtrees are recursively built the same way from the sub-arrays to its left and right; this can be done in O(n) time using a monotonic stack. The elegance of a Cartesian tree is that it turns a flat array into a tree structure without losing positional order — traversing it in-order gives back the array unchanged, while the heap property encodes the range-minimum relationships. This makes it the classic building block for solving Range Minimum Query (RMQ) in O(1) query time after O(n) preprocessing, by reducing RMQ to a Lowest Common Ancestor (LCA) problem on the Cartesian tree, since the LCA of two indices is exactly the minimum element of the range between them. Cartesian trees are also the deterministic analogue of a treap — a treap is essentially a Cartesian tree built over randomly assigned priorities instead of a fixed input sequence.
- Preserves original sequence order via in-order traversal
- Encodes range-minimum relationships via heap property
- Built in O(n) time with a monotonic stack
- Reduces RMQ to O(1) query via LCA after O(n) preprocessing
AI Mentor Explanation
A Cartesian tree over an innings' over-by-over run count is like promoting the over with the fewest runs conceded to sit as the overall reference point of a tree, with everything before it forming the left branch and everything after forming the right branch, recursively. Reading the tree left to right in order gives back the exact over sequence, unchanged. But the vertical structure — who is whose parent — always has the lowest-scoring over sitting above its neighbors. This lets an analyst instantly find the worst economy stretch between any two overs by finding where their branches first meet, without rescanning the whole innings each time.
Step-by-Step Explanation
Step 1
Find the minimum as root
The root of the Cartesian tree is the index of the minimum value in the current array segment.
Step 2
Recurse left and right
The left subtree is built from the sub-array left of the minimum, the right subtree from the sub-array to its right.
Step 3
Build in O(n) with a monotonic stack
Process elements left to right, maintaining a stack in increasing order, attaching popped nodes as left children to keep construction linear.
Step 4
Use for O(1) range-minimum queries
Reduce RMQ to LCA on the Cartesian tree: the LCA of two indices is the position of the minimum in the range between them.
What Interviewer Expects
- Explain in-order traversal recovers the original sequence
- Explain the heap property encodes range-minimum information
- Describe O(n) construction via a monotonic stack
- Connect Cartesian trees to solving RMQ via LCA
Common Mistakes
- Confusing a Cartesian tree with a treap (Cartesian tree uses fixed input values, treap uses random priorities)
- Forgetting in-order traversal must reproduce the exact original sequence
- Claiming construction is O(n log n) instead of the optimal O(n) with a monotonic stack
- Not knowing the RMQ-to-LCA reduction, a classic application
Best Answer (HR Friendly)
“A Cartesian tree turns an array into a tree without losing the array's order — reading the tree left to right gives back the original array — while also making the smallest element the root, and every subtree's smallest element its subtree's root. It's mainly used to answer 'what is the minimum value between these two positions' extremely fast, in constant time after building the tree once.”
Code Example
class CTNode:
def __init__(self, index, value):
self.index = index
self.value = value
self.left = None
self.right = None
def build_cartesian_tree(arr):
stack = [] # holds nodes in increasing value order
for i, val in enumerate(arr):
node = CTNode(i, val)
last_popped = None
while stack and stack[-1].value > val:
last_popped = stack.pop()
node.left = last_popped # everything smaller-index, larger-value hangs left
if stack:
stack[-1].right = node
stack.append(node)
return stack[0] if stack else None # bottom of stack is the rootFollow-up Questions
- How does a Cartesian tree reduce Range Minimum Query to Lowest Common Ancestor?
- How does a Cartesian tree relate to a treap?
- Why does the monotonic stack construction run in O(n) time?
- What happens to the Cartesian tree if the array has duplicate minimum values?
MCQ Practice
1. What does an in-order traversal of a Cartesian tree produce?
In-order traversal preserves positional order, reproducing the exact original array sequence.
2. What is the time complexity of building a Cartesian tree from an array of n elements using a monotonic stack?
A monotonic stack lets each element be pushed and popped at most once, giving O(n) total construction time.
3. How is Range Minimum Query (RMQ) solved using a Cartesian tree?
The LCA of two indices in the Cartesian tree corresponds exactly to the position of the minimum value in the range between them.
Flash Cards
What does in-order traversal of a Cartesian tree give back? — The original input sequence, unchanged.
What is the root of a Cartesian tree? — The index of the minimum (or maximum) value in the array segment.
What is the construction time complexity of a Cartesian tree? — O(n), using a monotonic stack.
What classic problem does a Cartesian tree solve in O(1) per query? — Range Minimum Query (RMQ), via reduction to Lowest Common Ancestor (LCA).