Trees (Nested Lists and Tree Recursion)

Practice tree-shaped data using a simple Tree ADT. You will (1) predict results of tree recursion, (2) trace a recursive computation that builds a tree of calls, and (3) implement + extend classic tree-recursive functions (fringe, then a pipeline computation).

0. Predict: First Match in Tree Search + Leaf Count

**Predict the output (4 lines)** before running. Write your prediction as comments first.

```python
# Tree ADT + example tree

def tree(lbl, branches=None):
    if branches is None:
        branches = []
    return [lbl] + list(branches)

def label(t):
    return t[0]

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

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

t = tree(3, [
    tree(1),
    tree(2, [tree(1), tree(1)])
])

# Two classic tree recursions

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

def find_path(t, target):
    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

print(find_path(t, 2))
print(find_path(t, 1))
print(find_path(t, 99))
print(count_leaves(t))
```

Questions:
1) What does each `print` line output?
2) Why does `find_path(t, 1)` return that particular path (hint: branch order)?

def tree(lbl, branches=None):
    if branches is None:
        branches = []
    return [lbl] + list(branches)

def label(t):
    return t[0]

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

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

t = tree(3, [
    tree(1),
    tree(2, [tree(1), tree(1)])
])

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

def find_path(t, target):
    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

# Prediction (write answers BEFORE running):
# Line 1 prints: 
# Line 2 prints: 
# Line 3 prints: 
# Line 4 prints: 

# Then run to check:
# print(find_path(t, 2))
# print(find_path(t, 1))
# print(find_path(t, 99))
# print(count_leaves(t))

For find_path: the base case is when the current node label equals the target.

Branches are searched left-to-right, and the function returns as soon as it finds a successful subpath.

For count_leaves: every leaf contributes 1; internal nodes contribute the sum of their branches.

def tree(lbl, branches=None):
    if branches is None:
        branches = []
    return [lbl] + list(branches)

def label(t):
    return t[0]

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

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

t = tree(3, [
    tree(1),
    tree(2, [tree(1), tree(1)])
])

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

def find_path(t, target):
    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

# Predicted outputs:
# find_path(t, 2)  -> [3, 2]
# find_path(t, 1)  -> [3, 1]   (first match is the left child)
# find_path(t, 99) -> None
# count_leaves(t)  -> 3

1. Trace: Fibonacci Builds a Tree of Calls

In this exercise, the **shape of the returned tree mirrors the recursion**.

1) Trace the recursive calls for `fib_tree(4)`.
   - List the calls in the order they are *initiated*.
   - Then show the return value (the node label) for each call as it unwinds.

2) Predict (then verify):
   - `label(fib_tree(4))`
   - `count_leaves(fib_tree(4))`

Code:
```python
def tree(lbl, branches=None):
    if branches is None:
        branches = []
    return [lbl] + list(branches)

def label(t):
    return t[0]

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

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

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

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])

ft4 = fib_tree(4)
print(label(ft4))
print(count_leaves(ft4))
```

Your trace should explain where the **base case** happens and how results are **combined**.

def tree(lbl, branches=None):
    if branches is None:
        branches = []
    return [lbl] + list(branches)

def label(t):
    return t[0]

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

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

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

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])

# TRACE (fill in with your own steps):
# Calls initiated (top-down):
# fib_tree(4)
# fib_tree(3)
# fib_tree(2)
# fib_tree(1)
# fib_tree(0)
# ... continue until complete
#
# Unwinding (bottom-up):
# fib_tree(0) returns tree(0)
# fib_tree(1) returns tree(1)
# fib_tree(2) returns label 1
# fib_tree(3) returns label ?
# fib_tree(4) returns label ?
#
# Prediction:
# label(fib_tree(4)) = 
# count_leaves(fib_tree(4)) = 

ft4 = fib_tree(4)
# Uncomment to verify after predicting:
# print(label(ft4))
# print(count_leaves(ft4))

Base case: `n <= 1` returns a leaf tree with label `n`.

Recursive case: build left and right subtrees, then label = label(left) + label(right).

The leaf count equals the number of base-case hits (calls where n is 0 or 1). For n=4, there are 5 such calls.

def tree(lbl, branches=None):
    if branches is None:
        branches = []
    return [lbl] + list(branches)

def label(t):
    return t[0]

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

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

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

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])

# One valid trace (calls initiated):
# fib_tree(4)
#   fib_tree(3)
#     fib_tree(2)
#       fib_tree(1)  -> returns 1
#       fib_tree(0)  -> returns 0
#     fib_tree(1)    -> returns 1
#   fib_tree(2)
#     fib_tree(1)    -> returns 1
#     fib_tree(0)    -> returns 0
# Unwinding labels:
# fib_tree(2) label = 1+0 = 1
# fib_tree(3) label = 1+1 = 2
# fib_tree(4) label = 2+1 = 3
# Leaves = base-case calls = 5

ft4 = fib_tree(4)
assert label(ft4) == 3
assert count_leaves(ft4) == 5

2. Implement + Extend: Fringe (SICP Ex 2.28) → Sum of Odd Squares

This exercise has two parts.

**Part A (Implement)**: Implement `fringe(t)`, which returns a Python list of the **leaf labels** of a tree from left to right.

**Part B (Extend)**: Using `fringe(t)` as a *conventional interface* (a flat list of leaves), implement `sum_odd_squares(t)`:
- take the leaf labels
- keep only the odd ones
- square them
- sum the squares

Example goal:
- If the leaf labels are `[1, 2, 3, 4]`, then `sum_odd_squares` should return `1^2 + 3^2 = 10`.

Starter setup (Tree ADT + example trees):
```python
def tree(lbl, branches=None):
    if branches is None:
        branches = []
    return [lbl] + list(branches)

def label(t):
    return t[0]

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

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

x = tree(0, [
    tree(1),
    tree(2, [tree(3), tree(4)]),
    tree(5)
])

xx = tree(99, [x, x])
```

Keep your solutions short and respect the abstraction barrier (use `label`, `branches`, `is_leaf`).

def tree(lbl, branches=None):
    if branches is None:
        branches = []
    return [lbl] + list(branches)

def label(t):
    return t[0]

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

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

x = tree(0, [
    tree(1),
    tree(2, [tree(3), tree(4)]),
    tree(5)
])

xx = tree(99, [x, x])

def fringe(t):
    """Return a list of leaf labels, left-to-right.

    >>> fringe(x)
    [1, 3, 4, 5]
    """
    # YOUR CODE HERE
    pass

def sum_odd_squares(t):
    """Sum of squares of odd leaf labels.

    >>> sum_odd_squares(x)  # odd leaves are 1,3,5
    35
    """
    # YOUR CODE HERE
    pass

# Optional quick checks (predict first, then run):
# print(fringe(x))
# print(fringe(xx))
# print(sum_odd_squares(x))

For fringe: base case is a leaf; return a one-element list containing its label.

For fringe: recursive case should combine (concatenate) the fringes of each branch from left to right.

For sum_odd_squares: start from `leaves = fringe(t)`, then use a comprehension to filter odds, square, and sum.

def tree(lbl, branches=None):
    if branches is None:
        branches = []
    return [lbl] + list(branches)

def label(t):
    return t[0]

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

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

x = tree(0, [
    tree(1),
    tree(2, [tree(3), tree(4)]),
    tree(5)
])

xx = tree(99, [x, x])

def fringe(t):
    if is_leaf(t):
        return [label(t)]
    out = []
    for b in branches(t):
        out += fringe(b)
    return out

def sum_odd_squares(t):
    leaves = fringe(t)
    return sum(v * v for v in leaves if v % 2 == 1)

assert fringe(x) == [1, 3, 4, 5]
assert fringe(xx) == [1, 3, 4, 5, 1, 3, 4, 5]
assert sum_odd_squares(x) == 35
assert sum_odd_squares(tree(7)) == 49