Python iterative tree traversal: shared nodes are not a tree

Operation contract

The dispatch hierarchy lists integer node IDs and ordered child lists. The walker pushes children in reverse order so a LIFO stack visits them in the original child order. A visited set rejects any repeated reachable node, including a cycle or two parents sharing one child, because this operation promises a tree rather than a general graph walk.

Failure and ownership boundary

All declared child endpoints must exist. The root traversal ignores disconnected components but validates their edge shapes first; the lesson does not claim it produces a complete traversal of every node in a forest. The graph and child lists are bounded and must remain unchanged during the walk. Python graph BFS: mark a vertex when it enters the queue intentionally permits a different revisit policy.

Working program

def hierarchy_preorder(children, root):
    if type(root) is not int or root not in children or len(children) > 64:
        raise ValueError("root or hierarchy budget")
    if any(type(node) is not int or len(edges) > 64 or any(type(child) is not int or child not in children for child in edges)
           for node, edges in children.items()):
        raise ValueError("invalid child reference")
    pending, seen, ordered = [root], set(), []
    while pending:
        node = pending.pop()
        if node in seen:
            raise ValueError("reachable cycle or shared child")
        seen.add(node); ordered.append(node)
        pending.extend(reversed(children[node]))
    return ordered

print(hierarchy_preorder({0: [1, 2], 1: [3], 2: [], 3: []}, 0))
try:
    hierarchy_preorder({0: [1, 2], 1: [2], 2: []}, 0)
except ValueError:
    print("shared child rejected")

Output

[0, 1, 3, 2]
shared child rejected

Costs and limits

Validation scans O(V+E) declared data. Traversal stores visited nodes and pending edges; for a valid reachable tree this is O(r) extra references for r reached nodes. General rejected graphs can enqueue more pending references before a repeat is found.

Common Mistakes

• Reversing the child push order is needed for left-to-right preorder.
• A tree promise must reject shared reachable children as well as cycles.

Connected lessons

Python graph BFS: mark a vertex when it enters the queue, Python topological sort: dependency order and cycle rejection, Python linked-list reversal: validate cycles before changing links.

Related Python operation checks

Python BST deletion: replace a two-child node with its successor, Python recursion: bound depth instead of raising the limit.

Follow the related contract

Python AVL insertion: rotate while preserving ordered keys and heights.