CS 61A

Structure and Interpretation of Computer Programs, Fall 2014

Instructor: John DeNero




Question | Contains

Define contains, which takes a non-rooted tree tree and a number n, and returns True if this tree contains the element n, and False otherwise. You may assume you have the function is_leaf(tree) defined for you.

def contains(tree, n):
    """
    >>> t1 = [1, [2, 3], [4, [4, 5]]]
    >>> t2 = [1, [2, 3], [4, [4]]]
    >>> contains(t1, 5)
    True
    >>> contains(t2, 5)
    False
    """
    ## YOUR CODE HERE ##
def contains(tree, n):
    if is_leaf(tree):
        return tree == n
    for branch in tree:
        if contains(branch, n):
            return True
    return False