Due at 11:59pm on Friday, 07/20/2018.

Lab Check-in 5 questions here.

Starter Files

Download lab09.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on okpy.org.

• Questions 1 through 4 must be completed in order to receive credit for this lab. Starter code for coding questions is in lab09.py.
• Questions 5 and 6 are optional. It is recommended that you complete these problems on your own time. Starter code for these questions is in lab09_extra.py.

Topics

Trees (Again)

Recall that a tree is a recursive abstract data type that has a label (the value stored in the root of the tree) and branches (a list of trees directly underneath the root).

We saw one way to implement the tree ADT -- using constructor and selector functions that treat trees as lists. Another, more formal, way to implement the tree ADT is with a class. Here is part of the class definition for Tree, which can be found in lab09.py:

class Tree:
    """
    >>> t = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
    >>> t.label
    3
    >>> t.branches[0].label
    2
    >>> t.branches[1].is_leaf()
    True
    """
    def __init__(self, label, branches=[]):
        for b in branches:
            assert isinstance(b, Tree)
        self.label = label
        self.branches = list(branches)

    def is_leaf(self):
        return not self.branches

Even though this is a new implementation, everything we know about the tree ADT remains true. That means that solving problems involving trees as objects uses the same techniques that we developed when first studying the tree ADT (e.g. we can still use recursion on the branches!). The main difference, aside from syntax, is that tree objects are mutable.

Here is a summary of the differences between the tree ADT implemented using functions and lists vs. implemented using a class:

Displaying Tree instances

Implementing trees as a class gives us another advantage: we can specify how we want them to be output by the interpreter by implementing the __repr__ and __str__ magic methods.

Here is the __repr__ method:

def __repr__(self):
    if self.branches:
        branch_str = ', ' + repr(self.branches)
    else:
        branch_str = ''
    return 'Tree({0}{1})'.format(self.label, branch_str)

With this implementation of __repr__, a Tree instance is displayed as the exact constructor call that created it:

>>> t = Tree(4, [Tree(3), Tree(5, [Tree(6)]), Tree(7)])
>>> t
Tree(4, [Tree(3), Tree(5, [Tree(6)]), Tree(7)])
>>> t.branches
[Tree(3), Tree(5, [Tree(6)]), Tree(7)]
>>> t.branches[0]
Tree(3)
>>> t.branches[1]
Tree(5, [Tree(6)])

Here is the __str__ method. You do not need to understand how this function is implemented.

def __str__(self):
    def print_tree(t, indent=0):
        tree_str = '  ' * indent + str(t.label) + "\n"
        for b in t.branches:
            tree_str += print_tree(b, indent + 1)
        return tree_str
    return print_tree(self).rstrip()

With this implementation of __str__, we can pretty-print a Tree to see both its contents and structure:

>>> t = Tree(4, [Tree(3), Tree(5, [Tree(6)]), Tree(7)])
>>> print(t)
4
  3
  5
    6
  7
>>> print(t.branches[0])
3
>>> print(t.branches[1])
5
  6

Binary Search Trees

A binary search tree (or BST) is a special type of tree that obeys the following constraints:

• Each node has at most two branches, a left and a right branch.
• All labels in the left branch of any node have a value less than or equal to the label at that node.
• All labels in the right branch of any node have a value greater than the label at the node.

Thus, these are BSTs:

These are not BSTs:

The following class implements BSTs. Because we constrain BSTs to have at most two branches, we will store each branch as left and right instance attributes rather than in a list. BST objects are recursive: each branch is also a BST. Note that there exists an empty BST, which wasn't true with regular trees; this allows us to construct trees with less than two branches.

class BST:
    """
    >>> bst1 = BST(4, BST(2, BST(1)))
    >>> bst1.max()
    4
    >>> bst1.min()
    1
    >>> bst2 = BST(6, BST(2, BST(1), BST(4)), BST(7, BST.empty, BST(9)))
    >>> bst2.max()
    9
    >>> bst2.min()
    1
    >>> 9 in bst2
    True
    >>> 10 in bst2
    False
    >>> bst3 = BST(6, BST(2, BST(1), BST(4)), BST(8, BST(7), BST(9)))
    >>> 7 in bst3
    True
    >>> 10 in bst3
    False
    """
    empty = ()

    def __init__(self, label, left=empty, right=empty):
        assert left is BST.empty or isinstance(left, BST)
        assert right is BST.empty or isinstance(right, BST)

        self.label = label
        self.left, self.right = left, right

        if left is not BST.empty:
            assert left.max() <= label
        if right is not BST.empty:
            assert label < right.min()

    def is_leaf(self):
        return self.left is BST.empty and self.right is BST.empty

    def __repr__(self):
        if self.is_leaf():
            return 'BST({0})'.format(self.label)
        elif self.right is BST.empty:
            left = repr(self.left)
            return 'BST({0}, {1})'.format(self.label, left)
        else:
            left, right = repr(self.left), repr(self.right)
            if self.left is BST.empty:
                left = 'BST.empty'
            template = 'BST({0}, {1}, {2})'
            return template.format(self.label, left, right)

    def max(self):
        """Returns max element in BST."""
        if self.right is BST.empty:
            return self.label
        return self.right.max()

    def min(self):
        """Returns min element in BST."""
        if self.left is BST.empty:
            return self.label
        return self.left.min()

    def __contains__(self, e):
        if self.label == e:
            return True
        elif e > self.label and self.right is not BST.empty:
            return e in self.right
        elif self.left is not BST.empty:
            return e in self.left
        return False

Required Questions

What Would Python Display?

Q1: WWPD: Trees

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q trees -u

Enter Function if you believe the answer is <function ...>, Error if it errors, and Nothing if nothing is displayed. Recall that Tree instances will be displayed the same way they are constructed.

>>> from lab07 import *
>>> t = Tree(1, Tree(2))
______
Error
>>> t = Tree(1, [Tree(2)])
>>> t.label
______
1
>>> t.branches[0]
______
Tree(2)
>>> t.branches[0].label
______
2
>>> t.label = t.branches[0].label
>>> t
______
Tree(2, [Tree(2)])
>>> t.branches.append(Tree(4, [Tree(8)]))
>>> len(t.branches)
______
2
>>> t.branches[0]
______
Tree(2)
>>> t.branches[1]
______
Tree(4, [Tree(8)])

Coding Practice

Q2: Cumulative Sum

Write a function cumulative_sum that mutates the Tree t so that each node's label becomes the sum of all labels in the subtree rooted at the node.

def cumulative_sum(t):
    """Mutates t so that each node's label becomes the sum of all labels in
    the corresponding subtree rooted at t.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative_sum(t)
    >>> t
    Tree(16, [Tree(8, [Tree(5)]), Tree(7)])
    """
    "*** YOUR CODE HERE ***"
    for b in t.branches:
        cumulative_sum(b)
    t.label = sum([b.label for b in t.branches]) + t.label

Use Ok to test your code:

python3 ok -q cumulative_sum

Q3: Leaves

Write a function leaves that returns a list of all the label values of the leaf nodes of a Tree.

def leaves(t):
    """Returns a list of all the labels 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 ***"
    if t.is_leaf():
        return [t.label]
    all_leaves = []
    for b in t.branches:
        all_leaves += leaves(b)
    return all_leaves

Use Ok to test your code:

python3 ok -q leaves

Q4: Insert

Implement the function insert, which takes in a BST and an value v and inserts v into the correct position in the BST by mutating it.

Hint: Try drawing out a few examples of inserting into a BST. What do you notice about every node that is inserted? Will an inserted value ever become the label of an inner (i.e. non-leaf) node?

Note: To check if a BST is empty, compare its identity to BST.empty:

>>> b = BST(3, BST(2))
>>> b is BST.empty
False
>>> b.right is BST.empty
True

def insert(bst, v):
    """
    >>> bst = BST(5, BST(3, BST(1), BST(4)), BST(10, BST.empty, BST(11)))
    >>> insert(bst, 2)
    >>> 2 in bst
    True
    >>> insert(bst, 7)
    >>> insert(bst, 6)
    >>> bst
    BST(5, BST(3, BST(1, BST.empty, BST(2)), BST(4)), BST(10, BST(7, BST(6)), BST(11)))
    """
    "*** YOUR CODE HERE ***"
    if v <= bst.label:
        if bst.left is BST.empty:
            bst.left = BST(v)
        else:
            insert(bst.left, v)
    else:
        if bst.right is BST.empty:
            bst.right = BST(v)
        else:
            insert(bst.right, v)

Use Ok to test your code:

python3 ok -q insert

Optional Questions

More trees practice

Q5: Same Shape

Write a function same_shape that returns True if two Trees have the same shape. Two trees have the same shape if and only if they have the same number of branches and each pair of corresponding children have the same shape.

def same_shape(t1, t2):
    """Returns whether two Trees t1, t2 have the same shape. Two trees have the
    same shape iff they have the same number of branches and each pair
    of corresponding branches have the same shape.

    >>> t, s = Tree(1), Tree(3)
    >>> same_shape(t, t)
    True
    >>> same_shape(t, s)
    True
    >>> t = Tree(1, [Tree(2), Tree(3)])
    >>> same_shape(t, s)
    False
    >>> s = Tree(4, [Tree(3, [Tree(2, [Tree(1)])])])
    >>> same_shape(t, s)
    False
    """
    "*** YOUR CODE HERE ***"
    return len(t1.branches) == len(t2.branches) and \
		all([same_shape(b1, b2) for b1, b2 in zip(t1.branches, t2.branches)])

Use Ok to test your code:

python3 ok -q same_shape

Q6: Reverse Other

Write a function reverse_other that mutates the tree such that labels on every other (odd-depth) level are reversed. For example, Tree(1,[Tree(2, [Tree(4)]), Tree(3)]) becomes Tree(1,[Tree(3, [Tree(4)]), Tree(2)]). Notice that the nodes themselves are not reversed; only the labels are.

def reverse_other(t):
    """Mutates the tree such that nodes on every other (odd-depth) level
    have the labels of their branches all reversed.

    >>> t = Tree(1, [Tree(2), Tree(3), Tree(4)])
    >>> reverse_other(t)
    >>> t
    Tree(1, [Tree(4), Tree(3), Tree(2)])
    >>> t = Tree(1, [Tree(2, [Tree(3, [Tree(4), Tree(5)]), Tree(6, [Tree(7)])]), Tree(8)])
    >>> reverse_other(t)
    >>> t
    Tree(1, [Tree(8, [Tree(3, [Tree(5), Tree(4)]), Tree(6, [Tree(7)])]), Tree(2)])
    """
    "*** YOUR CODE HERE ***"
    def reverse_helper(t, need_reverse):
        if t.is_leaf():
            return
        new_labs = [child.label for child in t.branches][::-1]
        for i in range(len(t.branches)):
            child = t.branches[i]
            reverse_helper(child, not need_reverse)
            if need_reverse:
                child.label = new_labs[i]
    reverse_helper(t, True)

Use Ok to test your code:

python3 ok -q reverse_other

More BSTs practice

Q7: Next Smallest Element

Write a function next_element that takes in a BST and a number N. It returns the smallest element that is larger than N. For example, if you have this tree:

  --8---   
 /      \  
 3-    10- 
/  \      \
1  6     14
  / \   /  
  4 7  13  

Then next_element(3) is 4, next_element(6) is 7, and next_element(7) is 8.

def next_element(bst, n):
    """
	This function takes in a BST and a number N and it returns the smallest
	element that is greater than N, or None if it has no such element.

    >>> t = BST(8, BST(3, BST(1), BST(6, BST(4), BST(7))), BST(10, BST.empty, BST(14, BST(13))))
    >>> next_element(t, 1)
    3
    >>> next_element(t, 3)
    4
    >>> next_element(t, 5)
    6
    >>> next_element(t, 7)
    8
    >>> next_element(t, 10)
    13
    >>> next_element(t, 14)
    >>> result = [1]
    >>> a = next_element(t, 1)
    >>> while a:
    ...   result += [a]
    ...   a = next_element(t, a)
    >>> result
    [1, 3, 4, 6, 7, 8, 10, 13, 14]
    """
    "*** YOUR CODE HERE ***"
    def next_or_default(t, n, default):
        """The smallest element in t greater than n, or default
        if there is no such element."""
        if t is BST.empty:
            return default
        elif t.label > n:
            return next_or_default(t.left, n, t.label)
        else:
            return next_or_default(t.right, n, default)
    return next_or_default(bst, n, None)

Use Ok to test your code:

python3 ok -q next_element