Lab 5: Trees

Due: Wednesday 10/07 @ 11:59pm
Points: 1
Download: lab05.zip

Attendance

You need to submit the lab problems in addition to attending to get credit for lab. Students in mega lab only need to submit the lab problems. Preceptor interviews are highly recommended but not required for lab submissions.

If you are in regular lab, your TA will come around during lab to check you in. If you didn't attend for a good reason (such as being sick), fill out this form (within 2 weeks of your lab): attendance form.

Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

Required Questions

Trees

Consult the drop-down if you need a refresher on trees. It's okay to skip directly to the questions and refer back here should you get stuck.

Trees

A Tree has a label and a list of branches, each of which is a Tree. A tree with no branches is called a leaf.

@dataclass
class Tree[T]:
    label: T
    branches: list[Tree[T]] = field(default_factory=list)  # branches defaults to []

def is_leaf(t: Tree) -> bool:
    "Return whether a Tree t is a leaf with no branches."
    return not t.branches

For example:

Tree(4) makes a leaf labeled 4.
u = Tree(5, [Tree(6), Tree(7)]) makes a tree labeled 5 with two leaves labeled 6 and 7.
t = Tree(3, [Tree(4), u]) makes a tree labeled 3 with two branches: a leaf labeled 4 and the tree u.

Example Tree

Printing a Tree shows each label on its own line, indented below its parent's label:

>>> u = Tree(5, [Tree(6), Tree(7)])
>>> t = Tree(3, [Tree(4), u])
>>> print(t)
3
  4
  5
    6
    7

The label of the second branch of t is t.branches[1].label, which is 5.

A node of Tree t is either itself or a Tree within it. A node's parent is the Tree for which it is a branch, and its children are its branches. The root node is t and has no parent. Leaves have no children. A path is a sequence of nodes in which each is the parent of the next.

This tree visualizer draws the structure of any tree.

Remember, for a tree t:

Its root label t.label can be any value.
Its branches are trees, and t.branches is a list of its branches.
An equivalent tree can be constructed with Tree(t.label, t.branches).
To check whether a tree t is a leaf, call is_leaf(t).
You can call functions that take a tree as an argument, such as sum_leaves(t).

def sum_leaves(t: Tree[int]) -> int:
    """Return the sum of the labels of the leaves of tree t.

    >>> t = Tree(3, [Tree(4), Tree(5, [Tree(6), Tree(7)])])
    >>> sum_leaves(t)  # 4 + 6 + 7
    17
    """
    if is_leaf(t):  # if t is a leaf,
        return t.label  # then the sum of its leaf labels is just its label
    return sum([sum_leaves(b) for b in t.branches])

The type Tree[int] describes a tree whose labels are all integers.

A type variable, such as T below, represents any type and expresses that the return value has the same type as the labels of the input tree.

def largest_leaf[T](t: Tree[T]) -> T:
    """Return the largest label of the leaves of tree t.

    >>> t = Tree(3, [Tree(4), Tree(5, [Tree(6), Tree(7)])])
    >>> largest_leaf(t)
    7
    """
    if is_leaf(t):  # if t is a leaf,
        return t.label  # then the largest leaf label is just its label
    return max([largest_leaf(b) for b in t.branches])

Q1: Sprout Leaves

Define a function sprout_leaves that takes in a tree t and a list of leaf labels leaves. It returns a new tree that is identical to t, but in which each old leaf node has new branches, one for each leaf label in leaves.

For example, say we have the tree t = Tree(1, [Tree(2), Tree(3, [Tree(4)])]):

If we call sprout_leaves(t, [5, 6]), the result is the following tree:

def sprout_leaves[T](t: Tree[T], leaves: list[T]) -> Tree[T]:
  """Sprout new leaves containing the labels in leaves at each leaf of
  the original tree t and return the resulting tree.

  >>> t = Tree(1, [Tree(2), Tree(3)])
  >>> print(t)
  1
    2
    3
  >>> print(sprout_leaves(t, [4, 5]))
  1
    2
      4
      5
    3
      4
      5

  >>> u = Tree(1, [Tree(2, [Tree(3)])])
  >>> print(u)
  1
    2
      3
  >>> print(sprout_leaves(u, [6, 1, 2]))
  1
    2
      3
        6
        1
        2
  """
  "*** YOUR CODE HERE ***"  # replace the code below
  return t

python3 -m pytest -k sprout_leaves

Q2: Path Sum

Define a function pathsum, 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.

def pathsum(t: Tree[int], n: int) -> bool:
  """Return whether there is a path from the root of t to a leaf whose
  labels sum to n.

  >>> t = Tree(2, [Tree(3, [Tree(5), Tree(7)]), Tree(4)])
  >>> pathsum(t, 12) # 2 -> 3 -> 7
  True
  >>> pathsum(t, 5)  # A path that doesn't reach a leaf such as 2 -> 3 doesn't count
  False
  """
  "*** YOUR CODE HERE ***"  # replace the code below
  return False

python3 -m pytest -k pathsum

Q3: Pruning Leaves

Implement prune_leaves, which takes a tree t and a tuple of values vals. It returns a version of t with all its leaves whose labels are in vals removed. Do not remove non-leaf nodes and do not remove leaves that do not match any of the items in vals. Return None if pruning the tree results in there being no nodes left in the tree.

def prune_leaves[T](t: Tree[T], vals: tuple[T, ...]) -> Tree[T] | None:
  """Return a version of t with all leaves that have a label
  that appears in vals removed.  Return None if the entire tree is
  pruned away.

  >>> t = Tree(2)
  >>> print(prune_leaves(t, (1, 2)))
  None
  >>> numbers = Tree(1, [Tree(2), Tree(3, [Tree(4), Tree(5)]), Tree(6, [Tree(7)])])
  >>> print(numbers)
  1
    2
    3
      4
      5
    6
      7
  >>> print(prune_leaves(numbers, (3, 4, 6, 7)))
  1
    2
    3
      5
    6
  """
  "*** YOUR CODE HERE ***"  # replace the code below
  return None

python3 -m pytest -k prune_leaves

Submit Assignment

Submit this assignment by running Provenance: Prepare Submission Bundle from the VS Code command palette and uploading the resulting zip to Gradescope. The zip already contains the files you've edited. Lab 00 has detailed instructions.

Your responses to WWPD questions are not submitted, and they do not need to be. Lab credit is based on the code writing questions.

Optional Questions

These questions are optional. If you don't complete them, you will still receive credit for this assignment. They are great practice, so do them anyway!

Q4: Perfectly Balanced

Implement sum_tree, which returns the sum of all the labels in tree t.

def sum_tree(t: Tree[int]) -> int:
  """Add all elements in a tree.

  >>> t = Tree(4, [Tree(2, [Tree(3)]), Tree(6)])
  >>> sum_tree(t)
  15
  """
  "*** YOUR CODE HERE ***"  # replace the code below
  return 0

python3 -m pytest -k sum_tree

Then, implement balanced, which returns whether every branch of t has the same total sum and the branches themselves are also balanced.

def balanced(t: Tree[int]) -> bool:
  """Checks if each branch has same sum of all elements and
  if each branch is balanced.

  >>> t = Tree(1, [Tree(3), Tree(1, [Tree(2)]), Tree(1, [Tree(1), Tree(1)])])
  >>> balanced(t)
  True
  >>> u = Tree(1, [t, Tree(1)])
  >>> balanced(u)
  False
  >>> t = Tree(1, [Tree(4), Tree(1, [Tree(2), Tree(1)]), Tree(1, [Tree(3)])])
  >>> balanced(t)
  False
  """
  "*** YOUR CODE HERE ***"  # replace the code below
  return False

python3 -m pytest -k balanced

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