Links

Slides

Concepts

1. What makes a tree recursively defined?
2. What does the label selector return? What does the branches selector return? Why is it wrong to do label(branches(t)), where t is a tree?
3. How can we process trees using recursion?

Problems

Question 1

Write a function that counts the number of occurences of x in lst.

def count(lst, x):
    "*** YOUR CODE HERE ***"

TOGGLE SOLUTION

def count(lst, x):
    if lst == []:
        return 0
    if lst[0] == x:
        return 1 + count(lst[1:], x)
    return count(lst[1:], x)

Question 2

Write a function that returns True if t only contains values from lst and False otherwise.

def tree_in_list(t, lst):
    "*** YOUR CODE HERE ***"

TOGGLE SOLUTION

def tree_in_list(t, lst):
    if root(t) not in lst:
        return False
    for b in branches(t):
        if not tree_in_list(b, lst):
            return False
    return True