Solutions: You can find the file with solutions for all questions here.

Trees

Question 1: Leaves

Write a function leaves that returns a list of all the entries of the leaf nodes of a Tree.

def leaves(t):
    """Returns a list of all the entries of the leaf nodes of the Tree t.

    >>> leaves(Tree(1))
    [1]
    >>> leaves(Tree(1, [Tree(2, [Tree(3)]), Tree(4)]))
    [3, 4]
    """
    if t.is_leaf():
        return [t.value]
    all_leaves = []
    for b in t.branches:
        all_leaves += leaves(b)
    return all_leaves

Use OK to test your code:

python3 ok -q leaves

Question 2: Path

Write a function path that returns the path from the root of the tree to the given entry value if it exists and [] if it does not. You can assume all entries are unique.

def path(t, value):
    """
    >>> t = Tree(9, [Tree(7, [Tree(3), Tree(2)]), Tree(5)])
    >>> path(t, 2)
    [9, 7, 2]
    >>> path(t, 5)
    [9, 5]
    >>> path(t, 8)
    []
    """
    if t.value == value:
        return [value]
    elif t.is_leaf():
        return []
    else:
        for b in t.branches:
            rest = path(b, value)
            if rest:
                return [t.value] + rest
        return []

Use OK to test your code:

python3 ok -q path

Question 3: Find Level

Implement find_level, which takes a tree t and an integer level and returns a list of all the entries that have depth level. If no such entries exists, return the empty list. For a refresher on the depth of a node, check out here.

def find_level(t, level):
    """
    >>> t = Tree(1, [Tree(2, [Tree(4), Tree(5)]), Tree(6, [Tree(7)])])
    >>> find_level(t, 2)
    [4, 5, 7]
    >>> find_level(t, 1)
    [2, 6]
    >>> find_level(t, 5)
    []
    """
    if level == 0:
        return [t.value]
    elif t.is_leaf():
        return []
    else:
        lst = []
        for b in t.branches:
            lst += find_level(b, level - 1)
        return lst

Use OK to test your code:

python3 ok -q find_level

Submit

Make sure to submit this assignment by running:

python3 ok --submit