Trees

Poll: What's wrong with this recursive function?

def find_max(nums: list[int], index: int = 0) -> int:
    """Returns the maximum of the numbers in nums, starting from the given index"""
    if index == len(nums) - 1:
        return nums[index]
    else:
        max_of_rest: int = find_max(nums, index)
        if nums[index] < max_of_rest:
            return max_of_rest
        else:
            return nums[index]

1. It's missing a base case
2. It's missing a recursive case
3. The recursive case doesn't progress towards the base case
4. It has an "off-by-one bug"

Poll: What's wrong with this recursive function?

def countdown(n: int) -> None:
    """Prints numbers from n down to 0, one on each line"""
    if n > 0:
        print(n)
        countdown(n - 1)

1. It's missing a base case
2. It's missing a recursive case
3. The recursive case doesn't progress towards the base case
4. It has an "off-by-one bug"

Trees

It's a tree!

You may have seen trees like this decision tree:

Some tree terminology / rules:

• Each node may have data
• There is a root node (the start)
• Each node points to any number of child nodes
• Cycles are not permitted
• There are any number of leaf nodes (node with no children)

Source: https://www.reddit.com/r/ProgrammerHumor/comments/1pdvb8/and_here_we_can_see_a_complete_binary_tree_in_its/

In computer science, we draw our trees with the root at the top and the leaves at the bottom.

Search Algorithms

Let's use recursion to search for an element in a tree. (See slides at the end for images of the tree)

class Tree(Generic[T]):
    def __init__(self, root_data: Optional[T] = None) -> None:
        if root_data is None:
            self.root: Optional[Node[T]] = None
        else:
            self.root = Node[T](root_data)
    
    def __str__(self) -> str:
        return self.root.__str__()
    
    def __contains__(self, item: T) -> bool:
        return self.contains(item, self.root)
    
    def contains(self, item: T, node: Optional[Node[T]]) -> bool:
        if node is None:
            return False
        elif node.data == item:
            return True
        else:
            return self.contains(item, node.left) or self.contains(item, node.right)

tree: Tree[str] = Tree[str]('Entry way')

assert tree.root is not None
tree.root.left = Node[str]('Living room')

tree.root.left.right = Node[str]('Kitchen')

print('Kitchen' in tree)  # True
print('Bathroom' in tree)  # False

The algorithm we just wrote is called a Depth-First Search, since it explores "deep" in one area before moving on to other unexplored "shallow" places (closer to the root).

Poll: This is pseudocode for a Depth-First Search on a graph that is not a tree (because it has cycles). What's a good base case?

DFS(node):
    Base case:
        ???
    Recursive case:
        For each child:
            Add child to explored nodes
            DFS(child)

1. If the node is in the set of explored nodes, do nothing
2. If the node is a leaf, add it to the set of explored nodes
3. If the node is None, do nothing
4. If the node is None, add it to the set of explored nodes