Inorder traversal in Python
Visit left subtree, node, right subtree; yields sorted order on a binary search tree.
- File
inorder_traversal.py, 35 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/inorder-traversal/. The authors are listed in prov/JDE4T3.jsonl.
def inorder(left: list[int], right: list[int], root: int) -> list[int]:
"""Return the nodes of a binary tree in inorder (left subtree, node, right subtree).
The binary tree is rooted at `root` (or empty if root == -1), unweighted,
and has the nodes 0 .. n-1. left[x] and right[x] are the children of x,
or -1 for an empty subtree. The walk uses an explicit stack, so a tree of
height 10^5 needs no deep recursion. Time Θ(n), extra space Θ(h).
"""
n = len(left)
if len(right) != n or not -1 <= root < n:
raise ValueError("left and right must have the same length and root must be -1 or a node")
stack: list[int] = [] # @line L1
out: list[int] = []
x = root
pushes = 0
while x != -1 or stack: # @line L2
while x != -1: # @line L3
pushes += 1 # @line L4
if pushes > n:
raise ValueError("the links do not form a binary tree")
stack.append(x)
x = left[x]
x = stack.pop() # @line L5
out.append(x) # @line L6
x = right[x] # @line L7
return out # @line L8
def inorder_keys(left: list[int], right: list[int], root: int, key: list) -> list:
"""Return the keys of the nodes in inorder; sorted if the tree is a binary search tree."""
return [key[x] for x in inorder(left, right, root)]
test_inorder_traversal.py 118 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/inorder-traversal/. The authors are listed in prov/JDE4T3.jsonl.
import random
import pytest
from inorder_traversal import inorder, inorder_keys
LEFT = [1, 3, -1, -1, -1, -1]
RIGHT = [2, 4, 5, -1, -1, -1]
KEY = [50, 30, 70, 20, 40, 80]
def recursive_inorder(left: list[int], right: list[int], x: int) -> list[int]:
if x == -1:
return []
return recursive_inorder(left, right, left[x]) + [x] + recursive_inorder(left, right, right[x])
def random_binary_tree(rng: random.Random, n: int) -> tuple[list[int], list[int], int]:
"""A random binary tree on 0 .. n-1 with a random root and random labels."""
if n == 0:
return [], [], -1
labels = list(range(n))
rng.shuffle(labels)
left = [-1] * n
right = [-1] * n
free = [(labels[0], 0), (labels[0], 1)]
for v in labels[1:]:
i = rng.randrange(len(free))
u, side = free[i]
free[i] = free[-1]
free.pop()
if side == 0:
left[u] = v
else:
right[u] = v
free.append((v, 0))
free.append((v, 1))
return left, right, labels[0]
def test_page_example():
assert inorder(LEFT, RIGHT, 0) == [3, 1, 4, 0, 2, 5]
assert inorder_keys(LEFT, RIGHT, 0, KEY) == [20, 30, 40, 50, 70, 80]
def test_empty_and_single():
assert inorder([], [], -1) == []
assert inorder([-1], [-1], 0) == [0]
def test_star():
# The largest star that is a binary tree: a root with two leaves.
assert inorder([1, -1, -1], [2, -1, -1], 0) == [1, 0, 2]
def test_deep_left_path():
n = 100_000
left = [i + 1 for i in range(n - 1)] + [-1]
right = [-1] * n
assert inorder(left, right, 0) == list(range(n - 1, -1, -1))
def test_deep_right_path():
n = 100_000
left = [-1] * n
right = [i + 1 for i in range(n - 1)] + [-1]
assert inorder(left, right, 0) == list(range(n))
def test_zigzag_path():
n = 100_001
left = [-1] * n
right = [-1] * n
for i in range(n - 1):
if i % 2 == 0:
left[i] = i + 1
else:
right[i] = i + 1
out = inorder(left, right, 0)
assert sorted(out) == list(range(n))
assert out[0] == 1 and out[-1] == 0
def test_bad_input():
with pytest.raises(ValueError):
inorder([0], [-1], 0)
with pytest.raises(ValueError):
inorder([-1], [-1, -1], 0)
with pytest.raises(ValueError):
inorder([-1], [-1], 1)
def test_random_against_recursive():
rng = random.Random(5)
for _ in range(600):
n = rng.randrange(0, 40)
left, right, root = random_binary_tree(rng, n)
assert inorder(left, right, root) == recursive_inorder(left, right, root)
def test_bst_gives_sorted_keys():
rng = random.Random(9)
for _ in range(200):
keys = rng.sample(range(1000), rng.randrange(1, 60))
left = [-1] * len(keys)
right = [-1] * len(keys)
for v in range(1, len(keys)):
x = 0
while True:
side = left if keys[v] < keys[x] else right
if side[x] == -1:
side[x] = v
break
x = side[x]
assert inorder_keys(left, right, 0, keys) == sorted(keys)
What the next level needs
- the tests did not run in this build