A Binary Search Tree, also called an ordered or sorted binary tree, is a rooted binary tree data structure where each Node has up to two children. All values in the left subtree of a node are less than the value at the tree’s root, and all values in the right subtree of a node are greater than or equal to the value at the root. Therefore, both subtrees must also be binary search trees.

Binary Search Tree Implementation

class BinarySearchTree:
    # We create our node class as an internal to our BST class
    class __Node:
        def __init__(self, val, left=None, right=None):
            self.val = val
            self.left = left
            self.right = right

        def getVal(self):
            return self.val

        def setVal(self, newVal):
            self.val = newVal

        def getLeft(self):
            return self.left

        def getRight(self):
            return self.right

        def setLeft(self,newLeft):
            self.left = newLeft

        def setRight(self, newRight):
            self.right = newRight

        # Recursive traversal of the tree, calls __iter__ method on left subtree, yielding all elements,
        # then the root of the tree is yielded, then the right subtree, resulting in an inorder traversal of the tree.
        def __iter__(self):
            if self.left != None:
                for elem in self.left:
                    yield elem

            yield self.val

            if self.right != None:
                for elem in self.right:
                    yield elem

        # BST Class methods
    def __init__(self):
        self.root = None

    def insert(self, val):
        # The insert function is recursive. We do not pass a self-parameter.
        # Static function, not class method
        def __insert(root, val):
            if root == None:
                return BinarySearchTree.__Node(val)
            if val < root.getVal():
                # Recursively calls __insert on subtree,
                # Reassign the reference after inserting a new value into the tree
                root.setLeft(__insert(root.getLeft(), val))
            else:
                # Recursively calls __insert on subtree,
                # Reassign the reference after inserting a new value into the tree
                root.setRight(__insert(root.getRight(), val))
            return root
        # After inserting a new value, reassign root reference(possibly to same Node)
        # to the new tree after inserting the new value.
        # Each time the __insert function is called, a new tree is returned
        self.root = __insert(self.root, val)

    # Calls __iter__ else returns empty array
    def __iter__(self):
        if self.root != None:
            return self.root.__iter__()
        else:
            return [].__iter__()

def main():
    s = input("Enter a list of numbers: ")
    lst = s.split()
    tree = BinarySearchTree()

    for x in lst:
        tree.insert(float(x))
    for x in tree:
        print(x)

if __name__ == "__main__":
    main()

Our binary search tree produces a sorted list of values when traversed.

Enter a list of numbers: 5 8 2 1 4 9 6 7
1.0
2.0
4.0
5.0
6.0
7.0
8.0
9.0

Process finished with exit code 0

Our insert function is given a tree, which initially is None and the __insert function returns a new tree with our new value. Finally, the root is set equal to this new tree. Each time the __insert function is called, a new tree is returned, and our root is reassigned, often to the same Node. It doesn’t hurt our code to reassign references, and our code works quite nicely. Our recursive __insert always reassigns the reference after inserting the new value into the tree. Finally, the root reference is reassigned to the new tree after inserting the new value.

Our __iter__ uses recursion to traverse the tree. After all the elements in the left subtree are yielded, the root value is yielded, then the values in the right subtree are yielded, resulting in an inorder traversal of the tree.

Worse case insertion complexity is O(n^2) with an average case of O(log n), or O(n log n) for the insertion of n items.