Lab 15 - Trees
Due by 11:59pm on 2024-03-12.
Starter Files
Download lab15.zip. Inside the archive, you will find starter files for the questions in this lab.
Topics
Trees
In computer science, trees are recursive data structures like linked lists, as one tree will contain zero or more other trees within it. You may be able to think of them as Links with multple rests. They are widely used in various settings and can be implemented in many ways. The diagram below is an example of a tree.
Generally in computer science, you may see trees drawn “upside-down” like above. We say the root is the node where the tree begins to branch out at the top, and the leaves are the nodes where the tree ends at the bottom. Notice how each node can be considered a tree in and of itself.
Some terminology regarding trees:
- Parent Node: A node that has at least one branch.
- Child Node: A node that has a parent. A child node can only have one parent.
- Root: The top node of the tree. In our example, this is the 1 node.
- Label: The value stored at a node. In our example, every node’s label is an integer.
- Leaf: A node that has no branches. In our example, the 4, 5, 6, 2 nodes are leaves.
- Branch: A subtree of the root. Trees have branches, which are trees themselves: this is why trees are recursive data structures.
- Edge: A connection between two nodes. For example, the line between nodes 3 and 6.
- Depth How far away a node is from the root. We define this as the number of edges between the root to the node. As there are no edges between the root and itself, the root has depth 0. In our example, the 3 node has depth 1 and the 4 node has depth 2.
- Height: The depth of the lowest (furthest from the root) leaf. In our example, the 4, 5, and 6 nodes are all the lowest leaves with depth 2. Thus, the entire tree has height 2.
In computer science, there are many different types of trees, used for different purposes, such as binary search trees (BST) or AVL trees (take CS235 to learn about them). Some vary in the number of branches each node has; others vary in the structure of the tree.
Tree Data Abstraction
A tree has a root value and a list of branches, where each branch is itself a tree.
The data abstraction specifies that accessing the branches attribute on a tree t will give us a list of branches. Treating the return value of t.branches as a list is then part of how we define trees.
How the entire tree t is implemented is under the abstraction barrier. Rather than assuming a pre-programmed implementation of label and branches, we will want to use those attributes directly to code our own implementation.
For example, we could choose to implement the tree data abstraction with a dictionary with separate entries for the label and the branches or as a list with the first element being label and the rest being branches.
- The tree constructor takes in a value
labelfor the root, and an optional list of branchesbranches. If branches isn’t given, the constructor uses the empty list[]as the default, meaning the tree starts with no branches. - The
labelattribute returns the value of the tree node, while thebranchesattribute returns the list of branches of the tree. They are called byt.labelandt.branchesrespectively wheretis the tree. Remember that each branch in branches is its own tree. - The
is_leaf()method returnsTrueif the tree has no branches andFalseotherwise.
With this in mind, we can create the tree from earlier using our constructor:
class Tree:
def __init__(self, label, branches=[]):
self.label = label
self.branches = list(branches)
def is_leaf(self):
return not self.branchesA more thorough implementation would be:
class Tree:
def __init__(self, label, branches=[]):
"""
A Tree is constructed by passing a label and an optional *list* of branches.
The list passed must only contain objects of the Tree class.
"""
self.label = label
for branch in branches:
assert isinstance(branch, Tree)
self.branches = list(branches)
def is_leaf(self):
"""
Returns a boolean, true if this Tree object is a leaf (has no branches), false otherwise.
"""
return not self.branches
def __repr__(self):
if self.branches:
branch_str = ', ' + repr(self.branches)
else:
branch_str = ''
return f'Tree({self.label}{branch_str})'
def __str__(self):
def indented(self):
lines = []
for b in self.branches:
for line in indented(b):
lines.append(' ' + line)
return [str(self.label)] + lines
return '\n'.join(indented(self))This implemenation is what this lab uses.
Tree Abstraction Barrier
Consider a tree t constructed by calling Tree(1, [Tree(2), Tree(4)]). For each of the following expressions, find what it evaluates to (hint: draw out the tree!):
t.labelt.branchest.branches[0].labelt.branches[1].is_leaf()
Answers:
1[Tree(2), Tree(4)]2True
Recursing Through Trees
Recursion with trees can be difficult, but if you first consider the simpliest case and slowly build on it, it will be easier. The following are questions to consider:
What should the function do...
- If there is a single tree without any branches? This will likely be a base case.
- If there is a tree with two branches that are also leaves?
- You will likely recursively call your function on the branches. What will recrusively calling your function on a branch return and how can you use it?
- If there is a tree with branches that have their own branches? This question is more rarely applicable, but may still be useful.
There are multiple ways to recurse through tree, but the following is likely the most common way:
def sum_tree(t):
"""Sum all the labels in a tree"""
if t.is_leaf():
return t.label
else:
total = 0
total += t.label
for branch in t.branches:
branch_sum = sum_tree(branch)
total += branch_sum
return totalWhat is the base case? What is happening when we call sum_tree on each of the branches?
You can also simplify sum_tree to something like this:
def sum_tree(t):
"""Sum all the labels in a tree"""
total = t.label
for branch in t.branches:
total += sum_tree(branch)
return totalDo you understand what this second form is doing? Why does it work as well? Discuss with your lab partners.
Required Questions
Q1: Finding Berries
The squirrels on campus need your help! There are a lot of trees on campus and the squirrels would like to know which ones contain berries. Define the function berry_finder, which takes in a tree and returns True if the tree contains a node with the value 'berry' and False otherwise.
Hint: To iterate through each of the branches of a particular tree, you can consider using a
forloop to get each branch.
def berry_finder(t):
"""Returns True if t contains a node with the value 'berry' and
False otherwise.
>>> scrat = Tree('berry')
>>> berry_finder(scrat)
True
>>> sproul = Tree('roots', [Tree('branch1', [Tree('leaf'), Tree('berry')]), Tree('branch2')])
>>> berry_finder(sproul)
True
>>> numbers = Tree(1, [Tree(2), Tree(3, [Tree(4), Tree(5)]), Tree(6, [Tree(7)])])
>>> berry_finder(numbers)
False
>>> t = Tree(1, [Tree('berry',[Tree('not berry')])])
>>> berry_finder(t)
True
"""
# Write your code hereQ2: Height
Write a function that returns the height of a tree. Recall that the height of a tree is the length of the longest path from the root to a leaf (starting at 0).
def height(t):
"""Return the height of a Tree.
>>> t = Tree(3, [Tree(5, [Tree(1)]), Tree(2)])
>>> height(t)
2
>>> t = Tree(3, [Tree(1), Tree(2, [Tree(5, [Tree(6)]), Tree(1)])])
>>> height(t)
3
"""
# Write your code hereQ3: Maximum Path Sum
Write a function that takes in a tree and returns the maximum sum of the values along any path in the tree. Recall that a path is from the tree’s root to any leaf picking only one branch at each step along the way.
def max_path_sum(t):
"""Return the maximum path sum of the Tree.
>>> t = Tree(1, [Tree(5, [Tree(1), Tree(3)]), Tree(10)])
>>> max_path_sum(t)
11
"""
# Write your code hereQ4: Find Path
Write a function that takes in a tree and a value x and returns a list containing the nodes along the path required to get from the root of the tree to a node containing x.
If x is not present in the tree, return None. Assume that the entries of the tree are unique, so there will only be one path to node x.
For the following tree, find_path(t, 5) should return [2, 7, 6, 5]
Hint: A framework has been provided for you, but feel free to disregard it if you find another way to solve the problem.
def find_path(t, x):
"""
>>> t = Tree(2, [Tree(7, [Tree(3), Tree(6, [Tree(5), Tree(11)])] ), Tree(15)])
>>> find_path(t, 5)
[2, 7, 6, 5]
>>> find_path(t, 10) # returns None
"""
if _____________________________:
return _____________________________
_____________________________:
path = ______________________
if _____________________________:
return _____________________________Submit
Submit the lab15.py file on Canvas to Gradescope in the window on the assignment page.
Extra Practice
Q5: Has Path
Write a function has_path that takes in a tree t and a string word. It returns True if there is a path that starts from the root where the entries along the path spell out the word, and False otherwise. (This data structure is called a trie, and it has a lot of cool applications, such as autocomplete). You may assume that every node's label is exactly one character.
def has_path(t, word):
"""Return whether there is a path in a Tree where the entries along the path
spell out a particular word.
>>> greetings = Tree('h', [Tree('i'),
... Tree('e', [Tree('l', [Tree('l', [Tree('o')])]),
... Tree('y')])])
>>> print(greetings)
h
i
e
l
l
o
y
>>> has_path(greetings, 'h')
True
>>> has_path(greetings, 'i')
False
>>> has_path(greetings, 'hi')
True
>>> has_path(greetings, 'hello')
True
>>> has_path(greetings, 'hey')
True
>>> has_path(greetings, 'bye')
False
>>> has_path(greetings, 'hint')
False
"""
assert len(word) > 0, 'no path for empty word.'
# Write your code hereTo solve this problem, we have to find all possible paths from the tree's root and check if the word is in one of those paths. It may be worth writing a helper function to help split these two tasks.