Class 23 - Intro to trees & Trees as recursive data

Date: November 4, 2026

⚠️Homework

Homework 8 due November 8, 2026

‼️Ending Skills

Last week for skills: 4

🆕New Skills

First week for skills: 6, 7

Skills: 8

Notes (review before class)

Ancestry Data in a Table

A medical study's ancestry data, one row per person ("" is an unknown parent):

ancestors = table(
    ["name", "birthyear", "eyecolor", "female-parent", "male-parent"],
    [
        ["Anna", 1997, "blue", "Susan", "Charlie"],
        ["Susan", 1971, "blue", "Ellen", "Bill"],
        ["Charlie", 1972, "green", "", ""],
        ["Ellen", 1945, "brown", "Laura", "John"],
        ["Bill", 1946, "blue", "", ""],
        ["John", 1922, "brown", "", "Robert"],
        ["Laura", 1922, "brown", "", ""],
        ["Robert", 1895, "blue", "", ""],
    ],
)

Questions: someone's grandparents? Each eye color's frequency? Is one person another's ancestor? How many generations?
Try: plan how to list someone's known grandparents (names are unique). Ours: find their parents, then their parents' parents, with a helper, parents_of.

Parents and Grandparents from a Table

import pytest

def parents_of(anc_table: Table, who: str) -> list[str]:
    """returns a list of the names of the known parents of who"""
    matches = anc_table.filter(lambda r: r["name"] == who)
    if matches.length() > 0:
        person_row = matches.row(0)
        names = [person_row["female-parent"], person_row["male-parent"]]
        return list(filter(lambda n: n != "", names))
    else:
        raise ValueError("No such person " + who)

def test_parents_of():
    assert parents_of(ancestors, "Anna") == ["Susan", "Charlie"]
    assert parents_of(ancestors, "John") == ["Robert"]
    assert parents_of(ancestors, "Robert") == []
    with pytest.raises(ValueError):
        parents_of(ancestors, "Paws")

"" isn't a name, and could break later computations, so we filter it out.
"Robert" (no known parents) gets []. "Paws" (not in the table) is a different case, and any list could be mistaken for names, so it's an error: raise ValueError(...) stops the program with a ValueError (as float causes for a non-number string) and our message.
with pytest.raises(ValueError): checks that the code under it causes that error (see Tests).
Test people missing a parent ("John", "Robert"), too.

Grandparents are the parents' parents:

def grandparents_of(anc_table: Table, who: str) -> list[str]:
    """returns a list of the known grandparents of who in the table"""
    plist = parents_of(anc_table, who)
    if len(plist) == 2:
        return parents_of(anc_table, plist[0]) + parents_of(anc_table, plist[1])
    elif len(plist) == 1:
        return parents_of(anc_table, plist[0])
    else:
        return []

def test_grandparents_of():
    assert grandparents_of(ancestors, "Anna") == ["Ellen", "Bill"]
    assert grandparents_of(ancestors, "Laura") == []
    assert grandparents_of(ancestors, "John") == []
    with pytest.raises(ValueError):
        grandparents_of(ancestors, "Paws")

Gotcha: with fewer than two parents, plist[1] (or plist[0]) is an error, so we check len(plist) first.

Ancestor Trees

Finding all ancestors this way needs recursion (how many generations?), and filters the table again and again. A family tree instead links each person to their parents. In data: a parent is a person, not a str (which leaves us back at the table), and people we know nothing about need their own variant:

from dataclasses import dataclass

@dataclass
class NoInfo:
    pass

@dataclass
class Person:
    name: str
    birthyear: int
    eye: str
    mother: "AncTree"
    father: "AncTree"

AncTree = NoInfo | Person

A tree holds hierarchical data: items with sub-items (a person's parents).
AncTree is a binary tree: conditional data, like a list, with a base case (NoInfo), but its recursive case has two self-referential fields (in quotes, as on Class 22).

anna_tree = Person("Anna", 1997, "blue",
                   Person("Susan", 1971, "blue",
                          Person("Ellen", 1945, "brown",
                                 Person("Laura", 1922, "brown", NoInfo(), NoInfo()),
                                 Person("John", 1922, "brown",
                                        NoInfo(),
                                        Person("Robert", 1895, "blue", NoInfo(), NoInfo()))),
                          Person("Bill", 1946, "blue", NoInfo(), NoInfo())),
                   Person("Charlie", 1972, "green", NoInfo(), NoInfo()))

ellen_tree = anna_tree.mother.mother

Nesting shows the structure. Naming subtrees first (robert_tree, then john_tree = Person("John", 1922, "brown", NoInfo(), robert_tree), ...) gives more examples, but hides it; field access digs them out instead.

Parents come from fields, not filtering:

def parents_of_tree(tr: AncTree) -> list[str]:
    """returns a list of the names of the parents at the root of tr"""
    match tr:
        case NoInfo():
            return []
        case Person(n, y, e, m, f):
            return [m.name, f.name]

Gotcha: this fails if a parent is NoInfo(), which has no name.

Recursive Functions on Trees: `in_tree`

Is a name in a tree? Tests first, covering both variants:

def test_in_tree():
    assert in_tree(anna_tree, "Anna")
    assert in_tree(anna_tree, "Ellen")
    assert not in_tree(ellen_tree, "Anna")
    assert not in_tree(NoInfo(), "Ellen")

The template (as for lists on Class 22): a case per variant, naming its pieces, and a recursive call on each piece of the same type:

# def in_tree(at: AncTree, name: str) -> bool:
#     match at:
#         case NoInfo():
#             ...
#         case Person(n, y, e, m, f):
#             ... in_tree(m, name) ... in_tree(f, name)

Fill in the ...s:

def in_tree(at: AncTree, name: str) -> bool:
    """returns whether name is in the tree"""
    match at:
        case NoInfo():
            return False
        case Person(n, y, e, m, f):
            # n is the same as at.name, and m is the same as at.mother
            return name == n or in_tree(m, name) or in_tree(f, name)

NoInfo() has no people: False.
A Person: the name is this person's, or in the mother's tree, or the father's (the recursive calls answer those).

Recap (20 mins)

A river network is a binary tree: streams merge into larger rivers, and each merge point joins exactly two upstream rivers. Read through the program:

from dataclasses import dataclass

@dataclass
class Merge:
    width: float
    left: "River"
    right: "River"

@dataclass
class Stream:
    flow_rate: float

River = Merge | Stream

stream_a = Stream(5)
stream_b = Stream(8)
stream_c = Stream(3)
merge_1 = Merge(12, stream_a, stream_b)
main_river = Merge(15, merge_1, stream_c)

# def river_fun(r: River) -> ...:
#     match r:
#         case Merge(width, left, right):
#             ... width ...
#             ... river_fun(left) ...
#             ... river_fun(right) ...
#         case Stream(flow):
#             ... flow ...

def total_flow(r: River) -> float:
    """returns the total flow rate of the streams that feed r"""
    match r:
        case Merge(width, left, right):
            return total_flow(left) + total_flow(right)
        case Stream(flow):
            return flow

def test_total_flow():
    assert total_flow(stream_a) == 5
    assert total_flow(main_river) == 16

Draw main_river as a tree. What is total_flow(merge_1)? What is total_flow(Merge(20, main_river, Stream(4)))?
Which parts of the template does total_flow keep, and which does it drop? Why doesn't it use width?
Why does test_total_flow check stream_a as well as main_river?

Class Exercises (35 mins)

Design a function count_streams that counts how many individual streams feed into a river network.
Design a function max_width that finds the maximum width among all merge points in a river network.
Design a function widen_river that takes a river network and a number, and returns a new network where every merge point is wider by that amount.
Design a function cap_flow that takes a river network and returns a new network where no stream has a flow rate above 10 (cap any higher values at 10).
Design a function has_large_stream that returns True if any stream in the network has a flow rate greater than 6.

Wrap-up (5 mins)

Binary trees naturally represent branching structures like river networks.
Recursive data definitions with multiple variants capture tree structure.
Recursive functions use match to handle each variant appropriately.
Tree processing often follows patterns: reductions (sum, count) and transformations (map-like operations).

Skills: 8​

Notes (review before class)​

Ancestry Data in a Table​

Parents and Grandparents from a Table​

Ancestor Trees​

Recursive Functions on Trees: in_tree​

Recap (20 mins)​

Class Exercises (35 mins)​

Wrap-up (5 mins)​