Rooted tree representation (left-child right-sibling) in Python
A way to store a rooted tree with arbitrary branching using, for each node, a pointer to its leftmost child and one to its next sibling.
- File
rooted_tree_representation.py, 116 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/rooted-tree-representation/. The authors are listed in prov/X6DGHS.jsonl.
from typing import Generic, Iterator, TypeVar
T = TypeVar("T")
class Node(Generic[T]):
"""A tree node with a key and three pointers: parent, leftmost child, next sibling."""
__slots__ = ("key", "p", "left_child", "right_sibling")
def __init__(self, key: T) -> None:
self.key = key
self.p: Node[T] | None = None
self.left_child: Node[T] | None = None
self.right_sibling: Node[T] | None = None
class RootedTree(Generic[T]):
"""Rooted trees of any degree in the left-child, right-sibling form.
Each node keeps three pointers whatever its number of children, so a tree
of n nodes takes Theta(n) space. new_node, add_child and parent cost O(1);
children(x) costs Theta(deg x); detach(y) costs O(deg of the parent of y);
preorder costs Theta(n) time and O(1) extra space.
"""
def new_node(self, key: T) -> Node[T]:
"""Return a new tree that has one node. Cost O(1)."""
return Node(key) # @line L1
def add_child(self, x: Node[T], y: Node[T]) -> None:
"""Make the root y the new leftmost child of x.
Precondition: y is a root (no parent, no sibling) and x is not in the
subtree of y. Cost O(1).
"""
if y.p is not None or y.right_sibling is not None:
raise ValueError("y must be a root")
y.p = x # @line L2
y.right_sibling = x.left_child # @line L3
x.left_child = y # @line L4
def parent(self, x: Node[T]) -> Node[T] | None:
"""Return the parent of x, or None for a root. Cost O(1)."""
return x.p
def children(self, x: Node[T]) -> Iterator[Node[T]]:
"""Yield the children of x from left to right. Cost Theta(deg x)."""
c = x.left_child # @line L5
while c is not None: # @line L6
yield c # @line L7
c = c.right_sibling
def preorder(self, r: Node[T]) -> list[T]:
"""Return the keys of the subtree of r in preorder. Theta(n) time, O(1) extra space besides the output."""
out: list[T] = []
x: Node[T] | None = r # @line L8
while x is not None: # @line L9
out.append(x.key) # @line L10
if x.left_child is not None: # @line L11
x = x.left_child
else:
while x is not r and x.right_sibling is None: # @line L12
x = x.p # type: ignore[assignment]
assert x is not None
x = None if x is r else x.right_sibling # @line L13
return out
def postorder(self, r: Node[T]) -> list[T]:
"""Return the keys of the subtree of r in postorder (children before the parent). Theta(n)."""
out: list[T] = []
x: Node[T] = r
while x.left_child is not None:
x = x.left_child
while True:
out.append(x.key)
if x is r:
return out
if x.right_sibling is not None:
x = x.right_sibling
while x.left_child is not None:
x = x.left_child
else:
assert x.p is not None
x = x.p
def detach(self, y: Node[T]) -> None:
"""Cut the subtree of y from its parent; y becomes a root. Cost O(deg of the parent)."""
x = y.p
if x is None:
return
if x.left_child is y:
x.left_child = y.right_sibling
else:
c = x.left_child
assert c is not None
while c.right_sibling is not y:
c = c.right_sibling
assert c is not None
c.right_sibling = y.right_sibling
y.p = None
y.right_sibling = None
def check_invariant(self, r: Node[T]) -> int:
"""Check that every child of each node points back to it; return the size of the subtree."""
count, stack = 0, [r]
while stack:
x = stack.pop()
count += 1
for c in self.children(x):
assert c.p is x
stack.append(c)
return count
test_rooted_tree_representation.py 121 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/rooted-tree-representation/. The authors are listed in prov/X6DGHS.jsonl.
import random
import pytest
from rooted_tree_representation import Node, RootedTree
def build_example() -> tuple[RootedTree[str], dict[str, Node[str]]]:
t: RootedTree[str] = RootedTree()
n = {k: t.new_node(k) for k in "ABCDEFG"}
for par, ch in [("A", "D"), ("A", "C"), ("A", "B"), ("B", "F"), ("B", "E"), ("D", "G")]:
t.add_child(n[par], n[ch])
return t, n
def test_example() -> None:
t, n = build_example()
assert [c.key for c in t.children(n["A"])] == ["B", "C", "D"]
assert n["B"].left_child is n["E"] and n["B"].right_sibling is n["C"]
assert t.parent(n["G"]) is n["D"] and t.parent(n["A"]) is None
assert t.preorder(n["A"]) == list("ABEFCDG")
assert t.postorder(n["A"]) == list("EFBCGDA")
assert t.preorder(n["B"]) == list("BEF") # a subtree stops at its root
assert t.check_invariant(n["A"]) == 7
def test_detach_and_edges() -> None:
t, n = build_example()
t.detach(n["C"]) # a middle child
assert [c.key for c in t.children(n["A"])] == ["B", "D"]
t.detach(n["B"]) # the leftmost child
assert [c.key for c in t.children(n["A"])] == ["D"]
assert t.preorder(n["B"]) == list("BEF")
t.add_child(n["G"], n["B"])
assert t.preorder(n["A"]) == list("ADGBEF")
t.detach(n["A"]) # a root: no change
leaf = t.new_node("z")
assert t.preorder(leaf) == ["z"] and t.postorder(leaf) == ["z"]
assert list(t.children(leaf)) == []
with pytest.raises(ValueError):
t.add_child(leaf, n["D"])
def test_deep_and_wide() -> None:
t: RootedTree[int] = RootedTree()
root = t.new_node(0)
x = root
for i in range(1, 100_000): # a path: no recursion limit is hit
y = t.new_node(i)
t.add_child(x, y)
x = y
assert t.preorder(root) == list(range(100_000))
assert t.postorder(root) == list(range(99_999, -1, -1))
wide = t.new_node(-1)
for i in range(1000):
t.add_child(wide, t.new_node(i))
assert [c.key for c in t.children(wide)] == list(range(999, -1, -1))
def oracle_pre(kids: dict[int, list[int]], r: int) -> list[int]:
out, stack = [], [r]
while stack:
x = stack.pop()
out.append(x)
stack.extend(reversed(kids[x]))
return out
def oracle_post(kids: dict[int, list[int]], r: int) -> list[int]:
return list(reversed(_mirror_pre(kids, r)))
def _mirror_pre(kids: dict[int, list[int]], r: int) -> list[int]:
out, stack = [], [r]
while stack:
x = stack.pop()
out.append(x)
stack.extend(kids[x])
return out
def test_random_against_child_lists() -> None:
rng = random.Random(3141)
for _ in range(500):
t: RootedTree[int] = RootedTree()
nodes = {0: t.new_node(0)}
kids: dict[int, list[int]] = {0: []}
par: dict[int, int | None] = {0: None}
in_tree = {0}
for step in range(rng.randint(0, 40)):
if rng.random() < 0.7 or len(in_tree) == 1:
k = len(nodes)
nodes[k] = t.new_node(k)
kids[k] = []
x = rng.choice(sorted(in_tree))
t.add_child(nodes[x], nodes[k])
kids[x].insert(0, k)
par[k] = x
in_tree.add(k)
else:
y = rng.choice(sorted(in_tree - {0}))
x = par[y]
assert x is not None
t.detach(nodes[y])
kids[x].remove(y)
sub = set(oracle_pre(kids, y))
in_tree -= sub
z = rng.choice(sorted(in_tree)) # re-attach the subtree elsewhere
t.add_child(nodes[z], nodes[y])
kids[z].insert(0, y)
par[y] = z
in_tree |= sub
for v in in_tree:
assert [c.key for c in t.children(nodes[v])] == kids[v]
assert (t.parent(nodes[v]) or Node(None)).key == par[v]
assert t.preorder(nodes[0]) == oracle_pre(kids, 0)
assert t.postorder(nodes[0]) == oracle_post(kids, 0)
assert t.check_invariant(nodes[0]) == len(in_tree)
What the next level needs
- the tests did not run in this build
Read the full page about Rooted tree representation (left-child right-sibling)