Lab 9 - More OOP, LLs, Trees

The first question is non conding - what would python do.

Instructions: https://inst.eecs.berkeley.edu/~cs61a/su19/lab/lab09/

Solution: https://github.com/tomthestrom/cs61a/blob/master/lab/lab09/lab09.py

Q2: Link to List

Write a function link_to_list that takes in a linked list and returns the sequence as a Python list. You may assume that the input list is shallow; none of the elements is another linked list.

def link_to_list(link):
    """Takes a linked list and returns a Python list with the same elements.

    >>> link = Link(1, Link(2, Link(3, Link(4))))
    >>> link_to_list(link)
    [1, 2, 3, 4]
    >>> link_to_list(Link.empty)
    []
    """
    "*** YOUR CODE HERE ***"

Q2: Solution

def link_to_list(link):
    """Takes a linked list and returns a Python list with the same elements.

    >>> link = Link(1, Link(2, Link(3, Link(4))))
    >>> link_to_list(link)
    [1, 2, 3, 4]
    >>> link_to_list(Link.empty)
    []
    """
    "*** YOUR CODE HERE ***"
    if link is Link.empty:
        return []
    else:
        return [link.first] + link_to_list(link.rest)

Q3: Store Digits

Write a function store_digits that takes in an integer n and returns a linked list where each element of the list is a digit of n.

def store_digits(n):
    """Stores the digits of a positive number n in a linked list.

    >>> s = store_digits(1)
    >>> s
    Link(1)
    >>> store_digits(2345)
    Link(2, Link(3, Link(4, Link(5))))
    >>> store_digits(876)
    Link(8, Link(7, Link(6)))
    """
    "*** YOUR CODE HERE ***"

Q3: Solution

def store_digits(n):
    """Stores the digits of a positive number n in a linked list.

    >>> s = store_digits(1)
    >>> s
    Link(1)
    >>> store_digits(2345)
    Link(2, Link(3, Link(4, Link(5))))
    >>> store_digits(876)
    Link(8, Link(7, Link(6)))
    """
    "*** YOUR CODE HERE ***"
    if n < 10:
        return Link(n)
    else:
        first_digit = int(str(n)[0])
        digit_cut = int(str(n)[1:])

        return Link(first_digit, store_digits(digit_cut))

Q4: Cumulative Sum

Write a function cumulative_sum that mutates the Tree t so that each node's label becomes the sum of all labels in the subtree rooted at the node

def cumulative_sum(t):
    """Mutates t so that each node's label becomes the sum of all labels in
    the corresponding subtree rooted at t.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative_sum(t)
    >>> t
    Tree(16, [Tree(8, [Tree(5)]), Tree(7)])
    """
    "*** YOUR CODE HERE ***"

Q5: Solution

def sum_tree(t):
    if t.is_leaf():
        return t.label
    else:
        for b in t.branches:
            t.label += sum_tree(b)
        return t.label
        
def cumulative_sum(t):
    """Mutates t so that each node's label becomes the sum of all labels in
    the corresponding subtree rooted at t.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative_sum(t)
    >>> t
    Tree(16, [Tree(8, [Tree(5)]), Tree(7)])
    """
    "*** YOUR CODE HERE ***"
    for branch in t.branches:
        t.label += sum_tree(branch)