A tree is a node with a value and a list of children. There is one root. No cycles. Directories, org charts, and parse trees are trees.

Goal

Build a tiny Kenya region tree, walk it, and count leaves.

A node

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = list(children or [])

kenya = Node(
    "Kenya",
    [
        Node("Coast", [Node("Mombasa")]),
        Node("Nyanza", [Node("Kisumu")]),
        Node("Rift", [Node("Nakuru"), Node("Eldoret")]),
        Node("Nairobi", []),
    ],
)
print(kenya.value, [c.value for c in kenya.children])

Walk

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = list(children or [])

def walk(node):
    out = [node.value]
    for child in node.children:
        out.extend(walk(child))
    return out

root = Node("Kenya", [Node("Mombasa"), Node("Kisumu")])
print(walk(root))

Preorder: the node, then each subtree.

Count leaves

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = list(children or [])

def leaves(node):
    if not node.children:
        return 1
    return sum(leaves(c) for c in node.children)

kenya = Node(
    "Kenya",
    [Node("Mombasa"), Node("Kisumu"), Node("Nairobi")],
)
print(leaves(kenya))

Tip

If a child can point back at a parent as a peer edge, you have a graph, not a tree. Next chapter.