Cartesian tree in Python
Binary tree whose inorder traversal is the array and which is heap-ordered by value.
- File
cartesian_tree.py, 80 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/cartesian-tree/. The authors are listed in prov/3X8X1H.jsonl.
from collections import deque
class CartesianTree:
"""The min-Cartesian tree of a sequence, built in O(n) time with a stack.
Node i is position i of the sequence (0 .. n-1). The tree is a rooted
binary tree: its inorder is 0, 1, ..., n-1, and every node holds a value
no smaller than its parent's. Equal values are ordered by position, so the
leftmost minimum of each range is the root of that range. Missing
children and the parent of the root are -1; root is -1 for n = 0.
"""
def __init__(self, values: list) -> None:
a = list(values)
n = len(a)
self.values = a
self.parent = [-1] * n
self.left = [-1] * n
self.right = [-1] * n
spine: list[int] = [] # @line L1
for i in range(n): # @line L2
last = -1 # @line L3
while spine and a[spine[-1]] > a[i]: # @line L4
last = spine.pop() # @line L5
self.left[i] = last # @line L6
if last != -1:
self.parent[last] = i
if spine: # @line L7
self.right[spine[-1]] = i
self.parent[i] = spine[-1]
spine.append(i) # @line L8
self.root = spine[0] if spine else -1 # @line L9
self.depth = [0] * n
if n:
queue = deque([self.root])
while queue:
x = queue.popleft()
for c in (self.left[x], self.right[x]):
if c != -1:
self.depth[c] = self.depth[x] + 1
queue.append(c)
def __len__(self) -> int:
return len(self.values)
def inorder(self) -> list[int]:
"""The nodes in inorder; equals list(range(n)) for every input."""
out: list[int] = []
stack: list[int] = []
x = self.root
while x != -1 or stack:
while x != -1:
stack.append(x)
x = self.left[x]
x = stack.pop()
out.append(x)
x = self.right[x]
return out
def range_min_index(self, i: int, j: int) -> int:
"""Position of the leftmost minimum of values[i..j], as lca(i, j).
The lowest common ancestor is found by climbing, in O(h) time for a
tree of height h; a constant-time LCA structure makes it O(1).
"""
if not 0 <= i <= j < len(self.values):
raise IndexError("need 0 <= i <= j < n")
u, v = i, j
while self.depth[u] > self.depth[v]:
u = self.parent[u]
while self.depth[v] > self.depth[u]:
v = self.parent[v]
while u != v:
u = self.parent[u]
v = self.parent[v]
return u
test_cartesian_tree.py 104 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/cartesian-tree/. The authors are listed in prov/3X8X1H.jsonl.
import random
import pytest
from cartesian_tree import CartesianTree
EXAMPLE = [3, 1, 4, 1, 5, 9, 2, 6]
def brute_parent(a: list) -> list[int]:
"""Parent array by the definition: the root of a[lo..hi] is its leftmost minimum."""
n = len(a)
parent = [-1] * n
work = [(0, n - 1, -1)] if n else []
while work:
lo, hi, p = work.pop()
if lo > hi:
continue
m = min(range(lo, hi + 1), key=lambda k: (a[k], k))
parent[m] = p
work.append((lo, m - 1, m))
work.append((m + 1, hi, m))
return parent
def test_page_example():
t = CartesianTree(EXAMPLE)
assert t.root == 1
assert t.parent == [1, -1, 3, 1, 6, 4, 3, 6]
assert t.left == [-1, 0, -1, 2, -1, -1, 4, -1]
assert t.right == [-1, 3, -1, 6, 5, -1, 7, -1]
assert t.depth == [1, 0, 2, 1, 3, 4, 2, 3]
assert t.inorder() == list(range(8))
assert t.range_min_index(4, 7) == 6
assert t.range_min_index(2, 5) == 3
assert t.range_min_index(0, 7) == 1
assert t.range_min_index(5, 5) == 5
def test_empty_and_single():
t = CartesianTree([])
assert t.root == -1 and t.inorder() == []
t = CartesianTree([42])
assert t.root == 0 and t.parent == [-1] and t.inorder() == [0]
assert t.range_min_index(0, 0) == 0
def test_increasing_is_right_path():
n = 100_000
t = CartesianTree(list(range(n)))
assert t.root == 0
assert t.right[:-1] == list(range(1, n))
assert all(x == -1 for x in t.left)
assert t.depth[-1] == n - 1
assert t.inorder() == list(range(n))
def test_decreasing_is_left_path():
n = 100_000
t = CartesianTree(list(range(n, 0, -1)))
assert t.root == n - 1
assert t.left[1:] == list(range(n - 1))
assert t.inorder() == list(range(n))
def test_equal_values_go_right():
t = CartesianTree([7] * 5)
assert t.root == 0 and t.parent == [-1, 0, 1, 2, 3]
assert t.range_min_index(2, 4) == 2
def test_star_shape():
# A small minimum in the middle with larger values on both sides.
t = CartesianTree([5, 0, 5])
assert t.root == 1 and t.left[1] == 0 and t.right[1] == 2
def test_bad_query():
t = CartesianTree(EXAMPLE)
with pytest.raises(IndexError):
t.range_min_index(3, 2)
with pytest.raises(IndexError):
t.range_min_index(0, 8)
def test_random_against_definition():
rng = random.Random(3)
for _ in range(700):
n = rng.randrange(0, 30)
a = [rng.randrange(0, rng.choice([3, 10, 1000])) for _ in range(n)]
t = CartesianTree(a)
assert t.parent == brute_parent(a)
assert t.inorder() == list(range(n))
for x in range(n):
if t.parent[x] != -1:
assert a[t.parent[x]] <= a[x]
for _ in range(5):
if n:
i = rng.randrange(n)
j = rng.randrange(i, n)
assert t.range_min_index(i, j) == min(range(i, j + 1), key=lambda k: (a[k], k))
What the next level needs
- the tests did not run in this build