BST_BASIC-insert+pretty-print.py

""" Basic BST code for inserting (i.e. building) and printing a tree

    Your ***second standard viva task*** (of 5) will be to implement a find method into
    the class BinaryTree from pseudocode. See the lab task sheet for Week 5. 

    Your ***first advanced viva task*** (of 3) will be to implement a remove (delete) method
    into the class Binary Tree from partial pseudocode. See the lab task sheet for Week 5 (available in Week 5).

    There will be some ***introductory challenges*** in Week 4, with solutions released in Week 5.
    It is STRONGLY RECOMMENDED you attempt these!

    Since the given code is in python it is strongly suggested you stay with python; but
    if you want to reimplement as C++ this is also OK (see the Week 5 lab sheet guidance). 
"""

import math

""" Node class
"""

class Node:
    def __init__(self, data = None):
        self.data = data
        self.left = None
        self.right = None

""" BST class with insert and display methods. display pretty prints the tree
"""

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, data):
        if self.root is None:
            self.root = Node(data)
        else:
            self._insert(data, self.root)

    def _insert(self, data, cur_node):
        if data < cur_node.data:
            if cur_node.left is None:
                cur_node.left = Node(data)
            else:
                self._insert(data, cur_node.left)
        elif data > cur_node.data:
            if cur_node.right is None:
                cur_node.right = Node(data)
            else:
                self._insert(data, cur_node.right)
        else:
            print("Value already present in tree")

    def display(self, cur_node):
        lines, _, _, _ = self._display(cur_node)
        for line in lines:
            print(line)


    def _display(self, cur_node):
        
        if cur_node.right is None and cur_node.left is None:
            line = '%s' % cur_node.data
            width = len(line)
            height = 1
            middle = width // 2
            return [line], width, height, middle

        if cur_node.right is None:
            lines, n, p, x = self._display(cur_node.left)
            s = '%s' % cur_node.data
            u = len(s)
            first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s
            second_line = x * ' ' + '/' + (n - x - 1 + u) * ' '
            shifted_lines = [line + u * ' ' for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2
        
        if cur_node.left is None:
            lines, n, p, x = self._display(cur_node.right)
            s = '%s' % cur_node.data
            u = len(s)
            first_line = s + x * '_' + (n - x) * ' '
            second_line = (u + x) * ' ' + '\\' + (n - x - 1) * ' '
            shifted_lines = [u * ' ' + line for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2

        left, n, p, x = self._display(cur_node.left)
        right, m, q, y = self._display(cur_node.right)
        s = '%s' % cur_node.data
        u = len(s)
        first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s + y * '_' + (m - y) * ' '
        second_line = x * ' ' + '/' + (n - x - 1 + u + y) * ' ' + '\\' + (m - y - 1) * ' '
        if p < q:
            left += [n * ' '] * (q - p)
        elif q < p:
            right += [m * ' '] * (p - q)
        zipped_lines = zip(left, right)
        lines = [first_line, second_line] + [a + u * ' ' + b for a, b in zipped_lines]
        return lines, n + m + u, max(p, q) + 2, n + u // 2
    # Iterative Binary Search Function
# this is an iteractive binary search method that takes in an array and a value in the array
# it uses binary search to return the index of the value if indeed it exists in the supplied array
# if its not, then the method returns a False bool.
def find_i(myArray, myValueToFind):
    # Here i am defining my 3 vatiables which represents, my lowest, middle and my highest value respectively
    
    lowestValue = 0
    highestValue = len(myArray) - 1
    middleValue = 0

    # here i am checking whether my lowest value is greater than my highest value, if it is
    # then i directly return false because the loop wont run, cases where my lowestvalue is less than
    # or equal to my highest value, i will first calculate my new middle value, by taking the sum of my
    # highest value and my lowest Value then divide that by 2 (since its binary) 
 
#  Looping through the values using the conditions defined above.
    while lowestValue <= highestValue:

        # finding my new middle value
 
        middleValue = (highestValue + lowestValue) // 2
 
        # If myValueToFind is greater, ignore left half
        #  if the value supplied to this method (myValueToFind) is greater than the middlevalue then 
        #  this ultimately means that my new lowest value will be in the other subset of the array,
        #  i can easily get that by taking my middleValue and adding 1 to it. This also means that I am 
        # ignoring the left half of myArray, since the value can never be in that section.
        if  myValueToFind > myArray[middleValue]:
            lowestValue = middleValue + 1
 
        # If myValueToFind is smaller, ignore right half
        #  In this code , I now check whether myValueToFind is smaller than my middle value, if it is
        #  I can now comfortably ignore the section to the right since the answer can never be in the subset
        elif myValueToFind < myArray[middleValue]:
            highestValue = middleValue - 1
 
        # means myValueToFind is present at middleValue
        # The last part of the if nesting will now mean that it is not in the left or the right subsection
        # but it exists, This programmatically denotes that the middle value is actually what we are looking 
        # for and the program returns the value.
        else:
            return middleValue
 
    # If we reach here, then the element was not present
    #  This codeblock will usually run whenever the loops conditions are not met, this also means
    # that the value i may be trying to search in my array doesnt even exist in the first place and i will
    # return with a False.
    return False


 
# This method returns the index of the value a user is searching for if it exists and responds with a 
#False if it cannot be found
# this method accepts a list that contains a value to be searched from the provided list, a lower value, higher 
def find_r(myList, lowestValue, highestValue, valueToSearch):
 
    # Here i first check if the value given lies in my search field, if not i terminate the program..
    # having the lowest value greater than my highest value will mean that the element is actually not
    # present in the myList
    if lowestValue <= highestValue:
        #I can now find my middle Value by dividing the sum of my highest and lowest value items by 2
 
        middleValue = (highestValue + lowestValue) // 2
 
        # 
        # At this point i will return the middlevalue if the value to search actually matches the middle value
        # this will mean that it it the actuall value we are searching for
        if valueToSearch == myList[middleValue]:
            return middleValue
 
  
        # In a case where the middle value is larger than the element we are searching for, this will
        # in this case mean that the element can only be found in the left part of the list
        elif valueToSearch <  myList[middleValue] :
            return find_r(myList, lowestValue, middleValue - 1, valueToSearch)
 
        # if the above logic doesnt pass, it means that the value we are searching for is on the remaining
        # right part of myList
        else:
            return find_r(myList, middleValue + 1, highestValue, valueToSearch)
 
    else:
        # This will return if the above code is jumped, and this ultimately means that the value we are looking
        # for is actually not in the list provided and therefore the programm will gracefully terminate with a False
        return False
# This code removes a node given a key and a root 
def remove(passedRoot, key):
    if passedRoot == None :
        return None
    if passedRoot.left == None and passedRoot.right == None:
        if passedRoot.key == key :
            return None
        else :
            return passedRoot
    key_node = None
    r = []
    r.append(passedRoot)
    temp = None
    while(len(r)):
        temp = r.pop(0)
        if temp.data == key:
            key_node = temp
        if temp.left:
            r.append(temp.left)
        if temp.right:
            r.append(temp.right)
    if key_node :
        b = temp.data
        key_node.data = b
    return passedRoot
  

#example calls, which construct and display the tree       
bst = BinaryTree()
bst.insert(4)
bst.insert(2)
bst.insert(6)
bst.insert(1)
bst.insert(3)
bst.insert(5)
bst.insert(7)
bst.insert(8)
bst.insert(9)
bst.insert(10)
bst.insert(11)
bst.insert(12)
bst.insert(13)
bst.insert(14)
bst.insert(15)
bst.insert(100)
bst.insert(200)

bst.display(bst.root)