Preorder traversal in Python
Visit each node before its subtrees; a DFS of a tree.
- File
preorder_traversal.py, 44 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/preorder-traversal/. The authors are listed in prov/K1CRY0.jsonl.
def preorder(children: list[list[int]], root: int = 0) -> list[int]:
"""Return the vertices of a rooted ordered tree in preorder.
The tree has the vertices 0 .. n-1 and is not weighted. children[v] lists
the children of v from left to right; root is the root. Precondition: the
lists describe a tree rooted at root (each vertex other than the root is in
exactly one list, and every vertex is reachable from the root). An empty
list of lists gives the empty order.
The stack holds one (vertex, next child index) pair for each vertex on the
path from the root, so there is no recursion. Time Theta(n), extra space
O(h) for the height h.
"""
if not children:
return []
out = [root] # @line L1
stack = [[root, 0]] # @line L2
while stack: # @line L3
top = stack[-1]
v, i = top # @line L4
if i < len(children[v]): # @line L5
top[1] = i + 1 # @line L6
c = children[v][i] # @line L7
out.append(c) # @line L8
stack.append([c, 0]) # @line L9
else:
stack.pop() # @line L10
return out # @line L11
def children_from_parents(parent: list[int]) -> tuple[list[list[int]], int]:
"""Turn a parent array (parent[root] = -1) into child lists in increasing order, and the root."""
children: list[list[int]] = [[] for _ in parent]
root = -1
for v, p in enumerate(parent):
if p < 0:
root = v
else:
children[p].append(v)
return children, root
test_preorder_traversal.py 64 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/preorder-traversal/. The authors are listed in prov/K1CRY0.jsonl.
import random
from preorder_traversal import children_from_parents, preorder
def oracle(children: list[list[int]], root: int) -> list[int]:
# Preorder is the lexicographic order of the root paths, written as child positions.
key = {root: ()}
todo = [root]
while todo:
v = todo.pop()
for i, c in enumerate(children[v]):
key[c] = key[v] + (i,)
todo.append(c)
return sorted(key, key=lambda v: key[v])
def test_example() -> None:
children = [[1, 2], [3, 4], [5], [], [6, 7], [], [], []]
assert preorder(children, 0) == [0, 1, 3, 4, 6, 7, 2, 5]
def test_single_vertex_and_empty() -> None:
assert preorder([[]], 0) == [0]
assert preorder([], 0) == []
def test_path_long() -> None:
n = 100_000
children = [[v + 1] for v in range(n - 1)] + [[]]
assert preorder(children, 0) == list(range(n))
def test_star() -> None:
n = 50
children = [list(range(1, n))] + [[] for _ in range(n - 1)]
assert preorder(children, 0) == list(range(n))
# the same star rooted at the leaf 1
children = [list(range(2, n)), [0]] + [[] for _ in range(n - 2)]
assert preorder(children, 1) == [1, 0] + list(range(2, n))
def test_child_order_matters() -> None:
assert preorder([[2, 1], [], []], 0) == [0, 2, 1]
def test_random_against_oracle() -> None:
rng = random.Random(7031)
for _ in range(600):
n = rng.randint(1, 40)
perm = list(range(n))
rng.shuffle(perm)
parent = [-1] * n
for i in range(1, n):
parent[perm[i]] = perm[rng.randrange(i)]
children, root = children_from_parents(parent)
for lst in children:
rng.shuffle(lst)
got = preorder(children, root)
assert got == oracle(children, root)
assert sorted(got) == list(range(n))
What the next level needs
- the tests did not run in this build