CS 61A

Structure and Interpretation of Computer Programs, Spring 2015

Instructor: John DeNero

Question | Filter Tree

Define filter_tree, which takes a non-rooted tree t and a function cond, and returns a new tree with only the elements of t that satisfy the function cond. All leaves which don't satisfy cond are replaced with empty lists.

def filter_tree(t, cond):
    """
    >>> t1 = [1, [2, 3], [3, [4, 3]]]
    >>> is_not_three = lambda x: x != 3
    >>> is_three = lambda x: x == 3
    >>> filter_tree(t1, is_three)
    [[], [[], 3], [3, [[], 3]]]
    >>> filter_tree(t1, is_not_three)
    [1, [2, []], [[], [4, []]]]

    """
    ## YOUR CODE HERE ##
def filter_tree(t, cond):
    if is_leaf(t):
        if fn(t):
            return t
        return []
    new_tree = [filter_tree(b, cond) for b in t]
    return new_tree