Trees

From flat lists to branching structure

When your data has 'parts of parts', a single list level is not enough.

• Last time: lists as universal sequences
• Today: trees as nested lists (closure property)
• Goal: recursive processing plans (count, map, search)

Closure property: lists can contain lists

x = [[1, 2], 3, 4]
print(x)

# Closure: we can put the whole structure inside another list
xx = [x, x]
print(xx)

• Leaves: non-list items
• Branches: sublists (subtrees)
• Tree recursion idea: solve smaller subtrees

A simple Tree ADT in Python

def tree(node_label, branches=None):
    if branches is None:
        branches = []
    # A tree is a list: [label, branch1, branch2, ...]
    return [node_label] + list(branches)

def label(t):
    return t[0]

def branches(t):
    return t[1:]

def is_leaf(t):
    return len(branches(t)) == 0

• Constructor: tree(label, branches)
• Selectors: label(t), branches(t), is_leaf(t)
• Abstraction barrier: do not index into $t$ directly

Visualize the example tree

• Root label: $3$
• Two children: $1$ and $2$
• Under $2$: two leaves, both $1$

Counting leaves: the first classic tree recursion

def count_leaves(t):
    if is_leaf(t):
        return 1
    return sum(count_leaves(b) for b in branches(t))
print(count_leaves(t))

• Base case: leaf $\Rightarrow 1$
• Recursive case: sum over branches
• Predict: count_leaves(t)

Tree map: transform every label, keep the shape

def tree_map(f, t):
    return tree(
        f(label(t)),
        [tree_map(f, b) for b in branches(t)]
    )

squared = tree_map(lambda x: x * x, t)
plus_one = tree_map(lambda x: x + 1, t)

print(label(plus_one))
print(squared)
print(plus_one)

• Transform: apply $f$ to each node label
• Rebuild: same branches, recursively mapped
• Checkpoint: root label after tree_map(lambda x: x + 1, t)

One recipe, three goals

$$ F(t)\;=\;\text{combine}\Big(\text{label}(t),\;[\,F(b)\;\text{for}\;b\in\text{branches}(t)\,]\Big) $$

• Aggregate: return a value (e.g., leaf count)
• Transform: return a new tree (e.g., map)
• Search: return evidence (e.g., a path) or $\text{None}$
• Always ask: base case for a leaf?

Searching a tree: find a path to a label

def find_path(t, target):
    """Return a list of labels from the root to target, or None."""
    if label(t) == target:
        return [label(t)]

    for b in branches(t):
        subpath = find_path(b, target)
        if subpath is not None:
            return [label(t)] + subpath

    return None

# Predict before you run:
# What do you think find_path(t, 2) returns?
print(find_path(t, 2))

# What do you think find_path(t, 1) returns?
print(find_path(t, 1))

# And what about a missing label?
print(find_path(t, 99))

• Predict: What path should we get for target 2? For target 1?
• Success: target at root
• Recursive attempt: try branches left-to-right (return the first path found)
• Why target 1 returns the left-child path: that branch is tried first, so we stop as soon as we find a match
• Failure: no branch works $\Rightarrow\;\text{None}$

The Fibonacci tree: recursion makes a tree of calls

def fib_tree(n):
    if n <= 1:
        return tree(n)
    left = fib_tree(n - 1)
    right = fib_tree(n - 2)
    return tree(label(left) + label(right), [left, right])

ft5 = fib_tree(5)
print(label(ft5))
print(count_leaves(ft5))

• Node label: Fibonacci value at that call
• Shape: two branches ($n-1$ and $n-2$)
• Leaf count for $n=5$: $8$ base cases

Exit ticket: predict, then justify

# Reminder setup for this exit ticket:
# t = ...   (the same tree used earlier in the lesson)
# def find_path(t, target): ...

print(find_path(t, 1))

• Practice: predict output of find_path(t, 1)
• Reflection: how did the base case control backtracking?