# Study Guide: Trees

## Instructions

This is a study guide with links to past lectures, assignments, and handouts, as well as additional practice problems to assist you in learning the concepts.

**Assignments**

Important: For solutions to these assignments once they have been released, see the main website

**Handouts**

**Lectures**

**Readings**

# Guides

## Trees

A **tree** is an abstract model of a hierarchical structure. It consists of
nodes with a parent-child relationship. Its name comes from the fact that when
drawn, it resembles an upside-down tree: the **root** of the tree is at the top
and the **leaves** are at the bottom.

A tree is a recursive data structure; each **node** of the tree contains a
**label** value and a list of **branches**, each of which are also trees. The
label can be *any* data type, while the branches are represented as a list of
trees. The lecture slides provide a good overview of tree terminology and a
visual to help demonstrate.

### Hierarchical Data

We learned in lecture about lists, containers which hold sequences of data. These sequences can also be arbitrarily nested to create nested lists.

```
>>> l = [1, 2, 3]
>>> [l, [l]]
[[1, 2, 3], [[1, 2, 3]]]
```

This results in a hierarchy that lets us model, organize, and represent complex systems.

Trees build upon this idea of hierarchy by constraining the structure of the
tree. We are only allowed to build trees in a certain way, and they take on a
certain visual representation, but underlying all of the nodes and their labels
and branches is the same story of a nested, list hierarchy. What the **tree
data abstraction** allows us to do is think of trees as larger units and not
worry about manipulating individual lists.

In this class, we have two different views of trees which we often switch between depending on the situation.

- We can
**view trees as individual nodes**. In Python, our tree data abstraction is compound type. This means that we reference it with a pointer or arrow, just like a list. But this means that, in our list of branches, each tree is pointed to with a pointer too! You can imagine this can get complicated quickly, so when we view trees as individual nodes, we consider what we can do with an individual node of a tree. Python sees trees this same way: not as a whole, but as an individual node in a larger structure that happens to be connected. - We can also
**view trees as larger, connected structures**. Just like functional abstraction allows us to reason about the behavior of a program in terms of its domain, range, and behavior, thinking abstractly about tree structures allow us to reason about the behavior of programs at a larger scale. We can say, for example, that calling`replace_thor_at_leaf`

on a branch of a tree will return a branch replacing all of its leaves' label values.

### Tree Traversal

Hierarchy and structure helps us organize data, but at the cost of making that very same data harder to find. Now that we've organized data into a tree, we'd like to be able to use and manipulate that data.

**Tree traversal** refers to the process of visiting each node in a tree data
abstraction, exactly once. Just like how we saw that we needed to come up with
an organized way to explore the space of possible solutions in tree recursion,
we also need an organized way to traverse trees to avoid repeating work or
getting stuck in an infinite loop.

Each node of a tree has a predefined structure: a label value and a list of branches. This structure lets us explore tree structures in a very specific pattern where we visit each node of the tree one-by-one until we've completed the traversal and solved the problem.

*Visit*the current node and check or otherwise*process*the node. Our base case often falls under this category: we process the node by checking if the node is a leaf, or some other stopping condition.- Iterate across the branches of the tree and recurse down. We often write a
`for`

loop or list comprehension to iterate across the branches of the tree and recurse on the branch to explore down the tree. - Combine the result obtained from the recursive call to determine the final result. To find the sum of all the label values in a tree, for example, it's not sufficient to stop at making a recursive call: we also need to determine what to do with the number returned from the sum of the values in the branch.

Tree problems tend toward recursive solutions. This also makes it convenient for understanding the structure of tree problems by first examining the expected behavior by coming up with small example cases. How should our program behave when we call it on a leaf, for example? How about if we scale up to a larger tree of 2 or 3 nodes? And so forth.

# Practice Problems

## Easy

### Q1: Tree Map

Define the function `tree_map`

, which takes in a tree and a
one-argument function as arguments and returns a new tree which is the
result of mapping the function over the entries of the input tree.

```
def tree_map(fn, t):
"""Maps the function fn over the entries of tree and returns the
result in a new tree.
>>> numbers = tree(1,
... [tree(2,
... [tree(3),
... tree(4)]),
... tree(5,
... [tree(6,
... [tree(7)]),
... tree(8)])])
>>> print_tree(tree_map(lambda x: 2**x, numbers))
2
4
8
16
32
64
128
256
"""
"*** YOUR CODE HERE ***"
if children(t) == []:
return tree(fn(label(t)), [])
mapped_subtrees = []
for subtree in children(t):
mapped_subtrees += [ tree_map(fn, subtree) ]
return tree(fn(label(t)), mapped_subtrees)
# Alternate solution
def tree_map(fn, t):
return tree(fn(label(t)), [tree_map(fn, t) for t in children(t)])
```

### Q2: Same shape

Define a function `same_shape`

that, given two trees, `t1`

and `t2`

,
returns `True`

if the two trees have the same shape (but not
necessarily the same data in each node) and `False`

otherwise.

```
def same_shape(t1, t2):
"""Return True if t1 is indentical in shape to t2.
>>> test_tree1 = tree(1, [tree(2), tree(3)])
>>> test_tree2 = tree(4, [tree(5), tree(6)])
>>> test_tree3 = tree(1,
... [tree(2,
... [tree(3)])])
>>> test_tree4 = tree(4,
... [tree(5,
... [tree(6)])])
>>> same_shape(test_tree1, test_tree2)
True
>>> same_shape(test_tree3, test_tree4)
True
>>> same_shape(test_tree2, test_tree4)
False
"""
"*** YOUR CODE HERE ***"
s1, s2 = branches(t1), branches(t2)
if len(s1) != len(s2):
return False
for index in range(len(s1)):
if not same_shape(s1[index], s2[index]):
return False
return True
# Alternate solution
def same_shape(t1, t2):
children_same = all(map(same_shape, branches(t1), branches(t2)))
return len(branches(t1)) == len(branches(t2)) and children_same
```