Postorder traversal in Python
Visit all children before the node; the basis of bottom-up evaluation.
- File
postorder_traversal.py, 46 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/postorder-traversal/. The authors are listed in prov/M0CFJK.jsonl.
def postorder(children: list[list[int]], root: int = 0) -> list[int]:
"""Return the vertices of a rooted ordered tree in postorder.
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. 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: list[int] = [] # @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
stack.append([children[v][i], 0]) # @line L7
else: # @line L8
stack.pop() # @line L9
out.append(v) # @line L10
return out # @line L11
def evaluate(children: list[list[int]], label: list[str], root: int = 0) -> int:
"""Evaluate an expression tree in postorder: a leaf holds an integer, an inner vertex '+' or '*'."""
value = [0] * len(children)
for v in postorder(children, root):
if not children[v]:
value[v] = int(label[v])
elif label[v] == "+":
value[v] = sum(value[c] for c in children[v])
else:
prod = 1
for c in children[v]:
prod *= value[c]
value[v] = prod
return value[root]
test_postorder_traversal.py 76 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/postorder-traversal/. The authors are listed in prov/M0CFJK.jsonl.
import random
from postorder_traversal import evaluate, postorder
INF = float("inf")
def oracle(children: list[list[int]], root: int) -> list[int]:
# Postorder sorts the root paths (child positions) with an end marker larger than any position.
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] + (INF,))
def test_example() -> None:
children = [[1, 2], [3, 4], [5], [], [6, 7], [], [], []]
assert postorder(children, 0) == [3, 6, 7, 4, 1, 5, 2, 0]
def test_expression() -> None:
# (2 + 3) * (4 + 1 + 5) = 50
children = [[1, 2], [3, 4], [5, 6, 7], [], [], [], [], []]
label = ["*", "+", "+", "2", "3", "4", "1", "5"]
assert evaluate(children, label) == 50
def test_single_vertex_and_empty() -> None:
assert postorder([[]], 0) == [0]
assert postorder([], 0) == []
def test_path_long() -> None:
n = 100_000
children = [[v + 1] for v in range(n - 1)] + [[]]
assert postorder(children, 0) == list(range(n - 1, -1, -1))
def test_star() -> None:
n = 50
children = [list(range(1, n))] + [[] for _ in range(n - 1)]
assert postorder(children, 0) == list(range(1, n)) + [0]
def test_children_before_parent() -> None:
rng = random.Random(11)
for _ in range(200):
n = rng.randint(1, 30)
parent = [-1] + [rng.randrange(i) for i in range(1, n)]
children = [[] for _ in range(n)]
for v in range(1, n):
children[parent[v]].append(v)
pos = {v: i for i, v in enumerate(postorder(children, 0))}
assert all(pos[v] < pos[parent[v]] for v in range(1, n))
def test_random_against_oracle() -> None:
rng = random.Random(4402)
for _ in range(600):
n = rng.randint(1, 40)
perm = list(range(n))
rng.shuffle(perm)
children = [[] for _ in range(n)]
for i in range(1, n):
children[perm[rng.randrange(i)]].append(perm[i])
for lst in children:
rng.shuffle(lst)
root = perm[0]
assert postorder(children, root) == oracle(children, root)
What the next level needs
- the tests did not run in this build