# Extra Questions

from lab11 import *

# Tree definition
class BinTree:
    empty = ()

    def __init__(self, label, left=empty, right=empty):
        self.label = label
        self.left = left
        self.right = right

    def __repr__(self):
        if self.left == self.empty and self.right == self.empty:
            return 'BinTree({})'.format(repr(self.label))
        left = 'BinTree.empty' if self.left == self.empty else repr(self.left)
        right = 'BinTree.empty' if self.right == self.empty else repr(self.right)
        return 'BinTree({}, {}, {})'.format(repr(self.label), left, right)

def binTree(tupleTree):
    """A convenience method for succinctly constructing binary trees.  The
    empty tuple or list stands for BinTree.empty; (V,) or [V] stands
    for BinTree(V); (V, T1, T2) or [V, T1, T2] stands for
    BinTree(V, binTree(T1), binTree(T2)).
    >>> binTree((3,
    ...          (1, (), [2]),
    ...          (6, [5], [7])))
    BinTree(3, BinTree(1, BinTree.empty, BinTree(2)), BinTree(6, BinTree(5), BinTree(7)))
    """
    if len(tupleTree) == 0:
        return BinTree.empty
    elif len(tupleTree) == 1:
        return BinTree(tupleTree[0])
    else:
        return BinTree(tupleTree[0], binTree(tupleTree[1]), binTree(tupleTree[2]))

def size(tree):
    """ Return the number of entries in the binary tree b.

    >>> b = BinTree(4,
    ...         BinTree(2,
    ...             BinTree(1)),
    ...         BinTree(6,
    ...             BinTree(5)))
    >>> size(b)
    5
    """
    "*** YOUR CODE HERE ***"

def contains(bst, elem):
    """
    >>> b = BinTree(5, BinTree(3, BinTree(2), BinTree(4)), BinTree(6))
    >>> contains(b, 5)
    True
    >>> contains(b, 6)
    True
    >>> contains(b, 7)
    False
    """
    "*** YOUR CODE HERE ***"

def unique(s):
    """Return a stream of the unique elements in s in the order that they
    first appear.

    >>> s = unique(lst_to_stream([1, 2, 2, 1, 0, 4, 2, 3, 1, 9, 0]))
    >>> s.first
    1
    >>> s.rest.first
    2
    >>> s.rest.rest.rest.rest.rest.first
    9
    """
    "*** YOUR CODE HERE ***"

def intersection(s1, s2):
    """Returns the intersection of two sets.

    >>> r = {0, 1, 4, 0}
    >>> s = {1, 2, 3, 4}
    >>> t = intersection(s, {3, 4, 2})
    >>> t
    {2, 3, 4}
    >>> intersection(r, t)
    {4}
    """
    "*** YOUR CODE HERE ***"

def union(s1, s2):
    """Returns the union of two sets.

    >>> r = {0, 6, 6}
    >>> s = {1, 2, 3, 4}
    >>> t = union(s, {1, 6})
    >>> t
    {1, 2, 3, 4, 6}
    >>> union(r, t)
    {0, 1, 2, 3, 4, 6}
    """
    "*** YOUR CODE HERE ***"