Trees

Question 1: Leaves

Write a function leaves that returns a list of all the values 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]
    """
    "*** YOUR CODE HERE ***"

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 value item if it exists and [] if it does not. You can assume all values are unique.

def path(t, item):
    """
    >>> 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)
    []
    """
    "*** YOUR CODE HERE ***"

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 values that have depth level. If no such values exist, 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)
    []
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q find_level

Submit

Make sure to submit this assignment by running:

python3 ok --submit