Mark Miyashita

This problem uses the Tree Class defined here.

In this problem we are going to be inserting an item into a binary search tree. Recall that a binary search tree means that all items on the left of the tree are less than the current entry and all items on the right of the tree are greater than the current entry. Note: We cannot insert into an empty tree because of our implementation. Since we are using None as our empty tree, we can’t add a .entry to None because it is not an object. This function should still work for all other trees though.

def insert(item, tree):
    """
    >>> t = Tree(5, Tree(1, None, Tree(4)), Tree(7, Tree(6), Tree(8)))
    >>> insert(2, t)
    >>> t
    Tree(5, Tree(1, None, Tree(4, Tree(2), None)), Tree(7, Tree(6), Tree(8)))
    """
    "***YOUR CODE HERE***"

Toggle Solution

def insert(item, tree):
    """
    >>> t = Tree(5, Tree(1, None, Tree(4)), Tree(7, Tree(6), Tree(8)))
    >>> insert(2, t)
    >>> t
    Tree(5, Tree(1, None, Tree(4, Tree(2), None)), Tree(7, Tree(6), Tree(8)))
    """
    if tree is None:
        return
    elif item < tree.entry:
        if tree.left:
            insert(item, tree.left)
        else:
            tree.left = Tree(item)
    else:
        if tree.right:
            insert(item, tree.right)
        else:
            tree.right = Tree(item)

I don't claim to be perfect so if you find an error on this page, please send me an email preferably with a link to this page so that I know what I need to fix!