jef

# -*- coding: utf-8 -*-
"""
Created on Wed Apr  1 17:30:17 2020

@author: joshm
"""

class Node(object):
    def __init__(self, key):
       self.left_child = None
       self.right_child = None
       self.value = key


    def setValue(self, new_value):
        self.value = new_value

    def getValue(self):
        return self.value

    def setLeft(self, new_value):
        self.left_child = new_value

    def getLeft(self):
        return self.left_child

    def setRight(self, new_value):
        self.right_child = new_value

    def getRight(self):
        return self.right_child


class BST(object):
    def __init__(self):
        self.root = None

    def insertNode(self,node):
        if self is None:
            self = node
            self.left_child = None
            self.right_child = None
        else:
            current = self.root
            while current is not None:
                if node.key < current.key:
                    if current.left_child is None:
                        current.left_child = node
                        current = None
                    else:
                        current = current.left_child
                else:
                    if current.right_child is None:
                        current.right_child = node
                        current = None
                    else:
                        current = current.right_child
            node.left_child = None
            node.right_child = None


    def searchNode(self,key):
        current = self.root
        while current is not None:
            if key == current.key:
                return current
            elif key < current.key:
                current = current.left_child
            else:
                current = current.right_child
        return None

    def deleteNode(self,key):
        par = None
        current = self.root
        while current is not None:
            if current.key == key:
                if not current.left_child and not current.right_child:
                    if not par:
                        self.root = None
                    elif par.left_child == current:
                        par.left_child = None
                    else:
                        par.right_child = None
                elif current.left_child and not current.right_child:
                    if not par:
                        self.root = current.left_child
                    elif par.left_child == current:
                        par.left_child = current.left_child
                    else:
                        par.right_child = current.left_child
                elif not current.left_child and current.right_child:
                    if not par:
                        self.root = current.right_child
                    elif par.left_child == current:
                        par.left_child = current.right_child
                    else:
                        par.right_child = current.left_child
                else:
                    successor = current.right_child
                    while successor.left_child is not None:
                        successor = successor.left_child
                    successorData = successor.value
                    deleteNode(self,successor.key)
                    current.value = successorData
                return
            elif current.key < key:
                par = current
                current = current.right_child
            else:
                par = current
                current = current.left_child
        return

    def createNode(parent, i, created, root):
        if created[i] is not None:
            return

        created[i] = Node(i)

        if parent[i] == -1:
            root[0] = created[i]
            return

        if created[parent[i]] is None:
            createNode(parent, parent[i], created, root)
        p = created[parent[i]]

        if p.left is None:
            p.left = created[i]

        else:
            p.right = created[i]

def createTree(parent):
    n = len(parent)

    created = [None for i in range(n+1)]

    root = [None]
    for i in range(n):
        createNode(parent, i, created, root)

    return root[0]

#Inorder traversal of tree
def inorder(root):
    if root is not None:
        inorder(root.left)
        print(root.key,end="")
        inorder(root.right)

# Driver Method
parent = [-1, 0, 0, 1, 1, 3, 5]
root = createTree(parent)
print("Inorder Traversal of constructed tree")
inorder(root)