Skip to main content

Class 24 - More trees

Date: November 9, 2026

⚠️Homework
Homework 9 due November 15, 2026
🆕New Skills
First week for skills: 8

Skills: None​

Notes (review before class)​

Summarizing How to Approach Tree Problems​

Tree programs use the same recipe as lists:

  1. The data definition, including a base (leaf) case.
  2. Example trees.
  3. The def line: the function's name, parameters, and types.
  4. A test function.
  5. The template, with the cases and recursive calls (as for in_tree in Class 23's notes).
  6. Fill in the template for the problem.
  7. Run the tests.

Binary Search Trees​

  • A binary search tree (BST) stores values at ordered keys (often numbers), for quick lookup. Each node has a key, a value, and two subtrees.
  • Its invariant, a rule the types can't express (so we write it as a comment): keys are unique; keys in a node's left subtree are less than the node's key, and keys in its right subtree are greater.
  • So a lookup that misses at the root searches only one subtree; if the subtrees are about the same size, each step rules out half the nodes.
  • The worst case follows the longest path from the root to an empty leaf: the tree's height (computed with max(a, b), the larger of two numbers).
  • In a balanced tree (subtrees of about the same size, at every level), the height is about log₂ n, for n nodes; a list may need to look at all n. For n = 1,000,000, that's about 20 vs. 1,000,000.

Study Questions​

  • Writing in_tree on a table (with filter) vs. on a tree: how many name comparisons might each make?
  • Why do we need a recursive function to process a tree?
  • In what order does in_tree check the names?

For practice, count a tree's blue-eyed people, its people, its generations, and the people with a given name.

Recap (20 mins)​

After Class 23's river networks, another binary tree: a BST with a number key and a string value at each node. Read through the program:

from dataclasses import dataclass

@dataclass
class EmptyLeaf:
    pass

@dataclass
class Node:
    key: int
    val: str
    left: "BST"
    right: "BST"

BST = EmptyLeaf | Node
# Invariant: keys are unique, and all nodes in the left
# subtree have keys less than the key in the current node,
# all nodes in the right subtree have keys greater than
# the key in the current node

BST0 = EmptyLeaf()
BST1 = Node(1, "hello", BST0, BST0)
BST2 = Node(5, "bye", BST1, BST0)
BST3 = Node(6, "bye", BST2, Node(10, "cs2000", BST0, BST0))

# def bst_temp(bst: BST) -> ...:
#     match bst:
#         case EmptyLeaf():
#             ...
#         case Node(k, v, left, right):
#             ... k ...
#             ... v ...
#             ... bst_temp(left) ...
#             ... bst_temp(right) ...

def height(bst: BST) -> int:
    """returns the number of nodes on the longest path from the root of bst
    to an EmptyLeaf"""
    match bst:
        case EmptyLeaf():
            return 0
        case Node(k, v, left, right):
            return 1 + max(height(left), height(right))

def test_height():
    assert height(BST0) == 0
    assert height(BST1) == 1
    assert height(BST2) == 2
    assert height(BST3) == 3
  • Draw BST3. Which keys are in its left subtree, and why must they be there? Which nodes would you visit looking for key 10? For key 7?
  • What is height(Node(20, "big", BST3, BST0))?
  • What would height compute if its last line were return 1 + height(left) + height(right)?

Class Exercises (35 mins)​

  1. The main goal of a BST is to be able to look up values at a given key. Design a function retrieve that takes a BST, a number, and returns a str | None (see Class 20) -- if the given number exists as a key in the tree, your function should return v, the string value that is on the node with the key. If the given number doesn't exist, your function should return None.

  2. In order for BSTs to have the performance characteristics that define them, they have to be balanced. This means not that each subtree is the same size (this would only allow trees that had number of elements equal to a power of 2), but rather, that each subtree is close to the size of the other. Rather than measuring size, often BSTs compare heights, calculated as we did with our height function above. Design a function is_balanced that should take a BST and return a boolean that indicates if the tree is balanced: this means that at every level, the height of the left and right subtrees differs by at most 1.

  3. Programs are also often tree shaped! In this exercise, we consider something simpler than full programs -- arithmetic expressions. Design a data definition Arith that allows you to represent numbers, addition of two arithmetic expressions, multiplication of two arithmetic expressions, division of two arithmetic expressions, and subtraction of two arithmetic expressions. This should be a binary tree with one leaf constructor (for numbers) and four node constructors (for the four types of binary operations).

  4. Define constants using your Arith to represent the following expressions:

1 + 2
1 * (3/4)
(7-3) * (2 + (5/2))
  1. Design a function evaluate (we can't call it eval, since Python already has a built-in function with that name) that takes an Arith and returns the single number to which it evaluates. If you use the three examples from exercise 4, your test cases should result in 3, 0.75, and 18.

Wrap-up (5 mins)​

  • BSTs are a powerful idea, and there are sophisticated algorithms to handle inserting and deleting data from them while maintaining balance. The core of their performance is exactly as you've seen, however.
  • Trees also show up in many other problems!