Trees

Question 1: Search

Write a function search that returns the Tree, whose root node is the given value if it exists and None if it does not. You can assume all entries are unique.

def search(t, value):
    """Searches for and returns the Tree whose entry is equal to value if
    it exists and None if it does not. Assume unique entries.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> search(t, 10)
    >>> search(t, 5)
    Tree(5)
    >>> search(t, 1)
    Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> search(t, 7)
    Tree(7)
    """
"*** YOUR CODE HERE ***"
if t.value == value: return t for branch in t.branches: result = search(branch, value) if result is not None: return result return

Use OK to test your code:

python3 ok -q search

Question 2: Cumulative Sum

Write a function cumulative_sum that returns a new Tree, where each value is the sum of all entries in the corresponding subtree of the old Tree.

def cumulative_sum(t):
    """Return a new Tree, where each value is the sum of all entries in the
    corresponding subtree of t.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative = cumulative_sum(t)
    >>> t
    Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative
    Tree(16, [Tree(8, [Tree(5)]), Tree(7)])
    >>> cumulative_sum(Tree(1))
    Tree(1)
    """
"*** YOUR CODE HERE ***"
subtrees = [cumulative_sum(st) for st in t.branches] new_entry = sum(st.value for st in subtrees) + t.value return Tree(new_entry, subtrees)

Use OK to test your code:

python3 ok -q cumulative_sum

Question 3: Add Leaves

Implement add_d_leaves, a function that takes in a Tree instance t and mutates it so that at each depth d in the tree, d leaves with labels v are added to each node at that depth. For example, we want to add 1 leaf with v in it to each node at depth 1, 2 leaves to each node at depth 2, and so on.

Recall that the depth of a node is the number of edges from that node to the root, so the depth of the root is 0. The leaves should be added to the end of the list of branches.

def add_d_leaves(t, v):
    """Add d leaves containing v to each node at every depth d.

    >>> t1 = Tree(1, [Tree(3)])
    >>> add_d_leaves(t1, 4)
    >>> t1
    Tree(1, [Tree(3, [Tree(4)])])
    >>> t2 = Tree(2, [Tree(5), Tree(6)])
    >>> t3 = Tree(3, [t1, Tree(0), t2])
    >>> add_d_leaves(t3, 10)
    >>> print(t3)
    3
      1
        3
          4
            10
            10
            10
          10
          10
        10
      0
        10
      2
        5
          10
          10
        6
          10
          10
        10
    """
    def add_leaves(t, d):
"*** YOUR CODE HERE ***"
for b in t.branches: add_leaves(b, d + 1) t.branches.extend([Tree(v) for _ in range(d)])
add_leaves(t, 0)

Use OK to test your code:

python3 ok -q add_d_leaves

Submit

Make sure to submit this assignment by running:

python3 ok --submit