btree_4.py

#! /usr/bin/python3
# ==================================================================
# Based on: www.youtube.com/watch?v=f5dU3xcE6ms
#       Python Data Structure #5, binary Search Tree (BST)
#
# Note: this code uses private helper functions
# ==================================================================

import numpy as np
from random import randint

class node:
    """binary search tree node"""
    def __init__(self,value=None):
        self.value = value
        self.left_child = None
        self.right_child = None

class binary_search_tree:
    """binary search tree"""
    def __init__(self):
        self.root = None

    def insert(self,value):
        """insert nodes into tree"""
        if self.root == None:
            self.root = node(value)
            print("insert {}  (root node)".format(value))
        else:
            self._insert(value,self.root)

    def _insert(self,value,cur_node):
        """insert nodes into tree - helper function"""
        if value < cur_node.value:
            if cur_node.left_child == None:
                cur_node.left_child = node(value)
                print("insert {}".format(value))
            else:
                self._insert(value,cur_node.left_child)
        elif value > cur_node.value:
            if cur_node.right_child == None:
                cur_node.right_child = node(value)
                print("insert {}".format(value))
            else:
                self._insert(value,cur_node.right_child)
        else:
            print("value {} is already in tree".format(value))

    def print_tree(self):
        """print tree in order one line per node"""
        if self.root != None:
            self._print_tree(self.root)
        else:
            print("Tree empty")

    def _print_tree(self,cur_node):
        """print tree in order one line per node - helper function"""
        if cur_node != None:
            self._print_tree(cur_node.left_child)
            print(str(cur_node.value))
            self._print_tree(cur_node.right_child)

    def print_tree_structure(self):
        """print tree structor in order"""
        if self.root != None:
            self._print_tree_structure(self.root,1)
        else:
            print("Tree empty")

    def _print_tree_structure(self,cur_node,n):
        """print tree structure in order - helper function"""
        if cur_node != None:
            self._print_tree_structure(cur_node.right_child,n+1)
            print("---"*n + " " + str(cur_node.value))
            self._print_tree_structure(cur_node.left_child,n+1)

    def height(self):
        """find maxmum tree height"""
        if self.root != None:
            return self._height(self.root,0)
        else:
            return 0

    def _height(self,cur_node,cur_height):
        """find maximum tree height - helper function"""
        if cur_node == None: return cur_height
        left_height = self._height(cur_node.left_child,cur_height+1)
        right_height = self._height(cur_node.right_child,cur_height+1)
        return max(left_height,right_height)


# ---- main --------------------------------------------------------

def large_tree(tree,num_elms=100,max_int=1000):
    """create a large test tree"""
    for _ in range(num_elms):
        cur_elem = randint(0,max_int)
        tree.insert(cur_elem)
    return tree

def small_tree(tree):
    """create a small test tree"""
    values = [5,2,7,9,6,3,10,4,1,2]
    print(values)
    for v in values:
        tree.insert(int(v))
    return tree

def worst_case_tree(tree):
    """create a small worst case test tree"""
    values = [10,9,7,5,4,3,2,1,11,12,13,14,15,16,17]
    print(values)
    print("------------------------------------------------------")
    for v in values:
        tree.insert(int(v))
    return tree


##tree = binary_search_tree()
##tree = large_tree(tree)
##tree.print_tree()

##tree = binary_search_tree()
##tree = small_tree(tree)
##tree.print_tree_structure()

tree = binary_search_tree()
print("------------------------------------------------------")
tree = worst_case_tree(tree)
print("------------------------------------------------------")
tree.print_tree_structure()

print("------------------------------------------------------")
print("Tree height is {}".format(str(tree.height())))