Homework # 8 (Due Date: Thursday November 10)

Submit your homework via E-learning

Name your file as StudentID_FirstName.py

Implement a binary search tree

class BSTree(object):
    ''' Implement a binary search tree.

    Each method you need to implement has its own docstring
    with further instruction. You'll want to move most of the
    implementation details to the Node class below.

    Additionally, keep count of the total number of Trees created
    and the number of Nodes in each tree. Include a class method,
    "num_trees" to return the former.

    def __init__(self):

    def __str__(self):
        ''' Return a representation of the tree as ({left} {elem} {right})
        where elem is the element stored in the root, and left and right
        are the left and right subtrees (which print out similarly).
        Empty trees should be represented by underscores.

    def __len__(self):
        ''' Returns the number of nodes in the tree.'''

    def __contains__(self, element):
        ''' Finds whether a given element is in the tree.
        Returns True if the element is found, else returns False.

    def insert(self, element):
        ''' Insert a given value into the tree.
        Our implementation will allow duplicate nodes. The left subtree
        should contain all elements <= to the current element, and the
        right subtree will contain all elements > the current element.

    def elements(self):
        ''' Return a list of the elements visited in an inorder traversal:
        Note that this should be the sorted order if you've inserted all
        elements using your previously defined insert function.

class Node(object):
    ''' A Node of the BSTree.
    Important data attributes: value (or element), left and right.

def main():

if __name__ == "__main__":