Mutable Trees: exam-level questions

If you need help reviewing Mutable Trees, take a look at these resources:

We will be using the OOP implementation of Trees from lecture, found here

Each question has a "Toggle Solution" button -- click it to reveal that question's solution.

Trees

Question 1

Implement a function equal which takes two trees and returns True if they satisfy all the following conditions:

  • The data of both Trees are equal
  • The Trees have the same number of children
  • All corresponding pairs of sub-Trees are also equal

    def equal(t1, t2):

    """Returns Tree if t1 and t2 are equal trees.
    
    >>> t1 = Tree(1,
    ...           [Tree(2, [Tree(4)]),
    ...            Tree(3)])
    >>> t2 = Tree(1,
    ...           [Tree(2, [Tree(4)]),
    ...            Tree(3)])
    >>> equal(t1, t2)
    True
    >>> t3 = Tree(1,
    ...           [Tree(2),
    ...            Tree(3, [Tree(4)])])
    >>> equal(t1, t3)
    False
    """
    "*** YOUR CODE HERE ***"
def equal(t1, t2):
    if t1.entry != t2.entry:
        return False
    elif len(t1.subtrees) != len(t2.subtrees):
        return False
    else:
        return all(equal(child1, child2) for child1, child2
                   in zip(t1.subtrees, t2.subtrees))

Question 2

Implement a function size that returns the number of elements in a given Tree.

def size(t):
    """Returns the number of elements in a tree.

    >>> t1 = Tree(1,
    ...           [Tree(2, [Tree(4)]),
    ...            Tree(3)])
    >>> size(t1)
    4
    """
    "*** YOUR CODE HERE ***"
def size(t):
    return 1 + sum([size(child) for child in t.subtrees])

Question 3

Implement a function height, which returns the height of a Tree. The height of a tree is defined as the number of branches from the root to the bottom-most leaf of the Tree.

By definition, a leaf has a height of 0, since there are 0 branches from the root to the root.

def height(t):
    """Returns the height of the tree.

    >>> leaf = Tree(1)
    >>> height(leaf)
    0
    >>> t1 = Tree(1,
    ...           [Tree(2, [Tree(4)]),
    ...            Tree(3)])
    >>> height(t1)
    2
    """
    "*** YOUR CODE HERE ***"
def height(t):
    if len(t.subtrees) == 0:
        return 0
    return 1 + max([height(child) for child in t.subtrees])

Question 4

Implement a function same_shape, which takes two Trees and returns True if the trees have the same structure, but not necessarily the same entries.

def same_shape(t1, t2):
    "*** YOUR CODE HERE ***"
def same_shape(t1, t2):
    if not t1.subtrees or not t2.subtrees:
        return not t1.subtrees and not t2.subtrees
    elif len(t1.subtrees) != len(t2.subtrees):
        return False
    for i in range(len(t1.subtrees)):
        if not same_shape(t1.subtrees[i], t2.subtrees[i]):
            return False
    return True

Question 5

Implement a function sprout_leaves, which takes a Tree and a list of values. For every leaf of the Tree, mutate it so that it has a list of branches where the items are the elements in the list of values.

def sprout_leaves(t, vals):
    "*** YOUR CODE HERE ***"
def sprout_leaves(t, vals):
    if not t.subtrees:
        t.subtrees = [Tree(v) for v in vals]
    else:
        for branch in t.subtrees:
            sprout_leaves(branch, vals)

Question 6

Implement a function prune_leaves, which takes a Tree and a list of values. For every leaf of the Tree, remove it if its entry is in the list of values.

def prune_leaves(t, vals):
    "*** YOUR CODE HERE ***"
def prune_leaves(t, vals):
    if not t.subtrees:
        if t.entry not in vals:
            return t
        else:
            return None
    new_branches = [prune_leaves(branch, vals) for branch in t.subtrees]
    t.subtrees = [b for b in new_branches if b is not None]
    return t

Binary Search Trees

Question 7

Implement two functions, max_bst and min_bst, which take a binary search tree and returns the maximum and minimum values, respectively.

def max_bst(b):
    "*** YOUR CODE HERE ***"
def max_bst(b):
    if b.right.is_empty:
        return b.entry
    return max_tree(b.right)
def min_bst(b):
    "*** YOUR CODE HERE ***"
def min_bst(b):
    if b.left.is_empty:
        return b.entry
    return min_tree(b.left)

Question 8

Implement the function contains, which takes a binary search tree and an item, and returns True if the binary search tree contains the item, and False if it doesn't.

def contains(b, item):
    """Returns True if B contains ITEM.

    >>> b1 = Tree(2,
    ...           Tree(1),
    ...           Tree(4, Tree(3)))
    >>> contains(b1, 4)
    True
    >>> contains(b1, 8)
    False
    """
    "*** YOUR CODE HERE ***"
def contains(b, item):
    if b is None:
        return False
    elif b.entry == item:
        return True
    elif b.entry > item:
        return contains(b.left, item)
    elif b.entry < item:
        return contains(b.right, item)

Question 9

Implement the function in_order, which takes a binary search tree, and returns a list containing its items from smallest to largest. In computer science, this is known as an in-order traversal.

def in_order(b):
    """Returns the items in B, a binary search tree, in sorted
    order.

    >>> b1 = Tree(2,
    ...           Tree(1),
    ...           Tree(4, Tree(3)))
    >>> in_order(b1)
    [1, 2, 3, 4]
    >>> singleton = Tree(4)
    >>> in_order(singleton)
    [4]
    """
    "*** YOUR CODE HERE ***"
def in_order(b):
    if b is None:
        return []
    else:
        left = in_order(b.left)
        right = in_order(b.right)
        return left + [b.entry] + right

Question 10

Implement a function nth_largest, which takes a binary search tree and a number n (greater than or equal to 1), and returns the nth largest item in the tree. For example, nth_largest(b, 1) should return the largest item in b. If n is greater than the number of items in the tree, return None.

Hint: You can assume there is a size function that returns the number of elements in a given tree.

def nth_largest(b, n):
    """Returns the Nth largest item in T.

    >>> b1 = Tree(2,
    ...           Tree(1),
    ...           Tree(4, Tree(3)))
    >>> nth_largest(b1, 1)
    4
    >>> nth_largest(b1, 3)
    2
    >>> nth_largest(b1, 4)
    1
    """
    "*** YOUR CODE HERE ***"
def nth_largest(b, n):
    if b is None:
        return None
    right = size(b.right)
    if right == n - 1:
        return b.entry
    elif right > n - 1:
        return nth_largest(b.right, n)
    elif right < n - 1:
        return nth_largest(b.left, n - 1 - right)