# Exam Prep 4: Trees

Students from past semesters wanted more content and structured time to prepare for exams. Exam Prep sections are a way to solidify your understanding of the week's materials. The problems are typically designed to be a bridge between discussion/lab/homework difficulty and exam difficulty.

**Reminder:** There is nothing to turn in and there is no credit given for attending Exam Prep Sections.

We try to make these problems **exam level** , so you are not expected to be able to solve them coming straight from lecture without additional practice.
To get the most out of Exam Prep, we recommend you **try these problems first on your own** before coming to the Exam Prep section, where we will explain how to solve these problems while giving tips and advice for the exam. Do not worry if you struggle with these problems, **it is okay to struggle while learning**.

You can work with anyone you want, including sharing solutions. We just ask you don't spoil the problems for anyone else in the class. Thanks!

You may only put code where there are underscores for the codewriting questions.

You can test your functions on their doctests by clicking the red test tube in the top right corner after clicking Run in 61A Code. Passing the doctests is not necessarily enough to get the problem fully correct. You must fully solve the stated problem.

### Q1: Perfectly Balanced and Pruned

**Difficulty: ⭐**

**Part A:** Implement `sum_tree`

, which takes adds together all the labels in a tree.

**Part B:** Implement `balanced`

, a function which takes in a tree and returns whether each of the branches have the same total sum, and each branch is balanced.

**Part C:** Implement `prune_tree`

, a function which takes in a tree `t`

as well as a function `predicate`

that returns True or False for each label of each tree node. `prune_tree`

returns a new tree where any node for which `predicate`

of the label of that node returns True, then all the branches for that tree are pruned (not included in the new tree).

**IMPORTANT:** You may use as many lines as you want for these two parts.

**Challenge:** Solve both of these parts with just 1 line of code each.

**Your Answer**Run in 61A Code

**Solution**

```
def sum_tree(t):
"""
Add all elements in a tree.
>>> t = tree(4, [tree(2, [tree(3)]), tree(6)])
>>> sum_tree(t)
15
"""
total = 0
for b in branches(t):
total += sum_tree(b)
return label(t) + total
# one line solution
return label(t) + sum([sum_tree(b) for b in branches(t)])
def balanced(t):
"""
Checks if each branch has same sum of all elements,
and each branch is balanced.
>>> t = tree(1, [tree(3), tree(1, [tree(2)]), tree(1, [tree(1), tree(1)])])
>>> balanced(t)
True
>>> t = tree(t, [t, tree(1)])
>>> balanced(t)
False
"""
if not branches(t):
return True
for b in branches(t):
if sum_tree(branches(t)[0]) != sum_tree(b) or not balanced(b):
return False
return True
# one line solution
return False not in [True] + [sum_tree(branches(t)[0]) == sum_tree(b) and balanced(b) for b in branches(t)]
def prune_tree(t, predicate):
"""
Returns a new tree where any branch that has the predicate of the label
of the branch returns True has its branches pruned.
>>> prune_tree(tree(1, [tree(2)]), lambda x: x == 1) # prune at root
[1]
>>> prune_tree(tree(1, [tree(2)]), lambda x: x == 2) # prune at leaf
[1, [2]]
>>> prune_tree(test_tree, lambda x: x >= 3) # prune at 3, 4, and 5
[1, [2, [4], [5]], [3]]
>>> sum_tree(prune_tree(test_tree, lambda x: x > 10)) # prune nothing, add 1 to 9
45
>>> prune_tree(test_tree, lambda x: x > 10) == test_tree # prune nothing
True
"""
if predicate(label(t)) or is_leaf(t):
return tree(label(t))
return tree(label(t), [prune_tree(b, predicate) for b in branches(t)])
# one line solution
return tree(label(t), [prune_tree(b, predicate) for b in branches(t) if not predicate(label(t))])
test_tree = tree(1,
[tree(2,
[tree(4,
[tree(8),
tree(9)]),
tree(5)]),
tree(3,
[tree(6),
tree(7)])])
draw(test_tree)
```

### Q2: Closest - Spring 2015 Midterm 2 Q3(c)

**IMPORTANT:** For this problem, you will be given time during the Exam Prep section to solve on your own before we go over it.

**Difficulty: ⭐⭐**

Implement `closest`

, which takes a tree of numbers `t`

and returns the smallest absolute difference anywhere in the tree between an entry and the sum of the entries of its branches. The sum only compares the any node value to the sum of its branches, or nodes one level below that node.

The built-in `min`

function takes a sequence and returns its minimum value.

**Reminder:** A branch of a branch of a tree t is not considered to be a branch of t.

**Your Answer**Run in 61A Code

**Solution**

```
def closest(t):
""" Return the smallest difference between an entry and the sum of the
root entries of its branches .
>>> t = tree(8 , [tree(4), tree(3)])
>>> closest(t) # |8 - (4 + 3)| = 1
1
>>> closest(tree(5, [t])) # Same minimum as t
1
>>> closest(tree(10, [tree(2), t])) # |10 - (2 + 8)| = 0
0
>>> closest(tree(3)) # |3 - 0| = 3
3
>>> closest(tree(8, [tree(3, [tree(1, [tree(5)])])])) # 3 - 1 = 2
2
>>> sum([])
0
"""
diff = abs(label(t) - sum([label(b) for b in branches(t)])) return min([diff] + [ closest (b) for b in branches(t)])
```

### Q3: Recursion on Tree ADT - Summer 2014 Midterm 1 Q7

**Difficulty: ⭐⭐**

Define a function `dejavu`

, which takes in a tree of numbers `t`

and a number `n`

. It returns `True`

if there is a path from the root to a leaf such that the sum of the numbers along that path is `n`

and `False`

otherwise.

**IMPORTANT:** For this problem, the starter code template is just a suggestion. You are welcome to add/delete/modify the starter code template, or even write your own solution that doesn’t use the starter code at all.

**Your Answer**Run in 61A Code

**Solution**

```
def dejavu(t, n):
"""
>>> my_tree = tree(2, [tree(3, [tree(5), tree(7)]), tree(4)])
>>> dejavu(my_tree, 12) # 2 -> 3 -> 7
True
>>> dejavu(my_tree, 5) # Sums of partial paths like 2 -> 3 don ’t count
False
"""
if is_leaf(t):
return n == label(t) for branch in branches(t): if dejavu(branch, n - label(t)): return True return False
```

### Q4: Forest Path - Fall 2015 Final Q3 (a)(b)(d)

**Difficulty: ⭐⭐⭐**

**Definition:** A *path* through a `tree`

is a list of adjacent node values that starts with the root value and ends with a leaf value. For example, the paths of `tree(1, [tree(2), tree(3, [tree(4), tree(5)])])`

are

```
[1, 2]
[1, 3, 4]
[1, 3, 5]
```

**Part A:** Implement `bigpath`

, which takes a tree `t`

and an integer `n`

. It returns the number of paths
in `t`

whose sum is at least `n`

. Assume that all node values of `t`

are integers.

**Part B:** Implement `allpath`

which takes a tree `t`

, a one-argument predicate `f`

, a two-argument reducing function `g`

, and a starting value `s`

. It returns the number of paths `p`

in `t`

for which `f(reduce(g, p, s))`

returns a truthy value. The `reduce`

function is in the code. Pay close attention to the order of arguments to the `f`

function in `reduce`

. You do not need to call it, though.

**Part C:** Re-implement `bigpath`

(Part A) using `allpath`

(Part B). Assume `allpath`

is implemented correctly.

**Your Answer**Run in 61A Code

**Solution**

```
def reduce(f, s, initial):
"""Combine elements of s pairwise
using f, starting with initial.
>>> reduce(mul, [2, 4, 8], 1)
64
>>> reduce(pow, [2, 3, 1], 2)
64
"""
for x in s:
initial = f(initial, x)
return initial
# The one function defined below is used in the questions below
# to convert truthy and falsy values into the numbers 1 and 0, respectively.
def one(b):
if b:
return 1
else:
return 0
def bigpath(t, n):
"""Return the number of paths in t that have a sum larger or equal to n.
>>> t = tree(1, [tree(2), tree(3, [tree(4), tree(5)])])
>>> bigpath(t, 3)
3
>>> bigpath(t, 6)
2
>>> bigpath(t, 9)
1
"""
if is_leaf(t):
return one(label(t) >= n) return sum([bigpath(b, n - label(t)) for b in branches(t)])
def allpath(t, f, g, s):
""" Return the number of paths p in t for which f(reduce(g, p, s)) is truthy.
>>> t = tree(1, [tree(2), tree(3, [tree(4), tree(5)])])
>>> even = lambda x: x % 2 == 0
>>> allpath(t, even, max, 0) # Path maxes are 2, 4, and 5
2
>>> allpath(t, even, pow, 2) # E.g., pow(pow(2, 1), 2) is even
3
>>> allpath(t, even, pow, 1) # Raising 1 to any power is odd
0
"""
if is_leaf(t):
return one(f(g(s, label(t)))) return sum([allpath(b, f, g, g(s, label(t))) for b in branches(t)])
from operator import add , mul
def bigpath_allpath(t, n):
"""Return the number of paths in t that have a sum larger or equal to n.
>>> t = tree(1, [tree(2), tree(3, [tree(4), tree(5)])])
>>> bigpath_allpath(t, 3)
3
>>> bigpath_allpath(t, 6)
2
>>> bigpath_allpath(t, 9)
1
"""
return allpath(t, lambda x: x >= n, add, 0)
```

### Q5: Extra Practice

**Difficulty: >⭐⭐⭐**