DSA Trees

How it works

The fixture describes an orchard inspection hierarchy using child lists. The traversal begins at a chosen root and visits children in an explicit deterministic order. Its input is trusted to be a finite acyclic tree with defined child entries. If received data can contain cycles or shared descendants, validate it or use a graph traversal with a visited policy rather than relying on these tree assumptions.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as tree-model.py and run python tree-model.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

def preorder_children(children, root):
    result, pending = [], [root]
    while pending:
        node = pending.pop()
        result.append(node)
        pending.extend(reversed(children[node]))
    return result

children = {"orchard":["north", "south"], "north":["oak"], "south":[], "oak":[]}
print(preorder_children(children, "orchard"))

Expected result

['orchard', 'north', 'oak', 'south']

Reversing the pushed child sequence makes the leftmost listed child come off the stack first. The hierarchy’s display order is a representation choice, not an intrinsic alphabetical property of trees. The returned list makes the observed order testable.

Time, space and assumptions

A valid tree with V vertices has V−1 edges, so this traversal is O(V). The output and worst-case pending stack use O(V) storage for this child-list implementation.