# BST (OOP Array/FreeSlot Linked List Implementation) -----------#

class Node:

    def __init__(self, data, ptr, leftPtr, rightPtr):
        self._data = data
        self._ptr = ptr
        self._leftPtr = leftPtr
        self._rightPtr = rightPtr

    def get_data(self):
        return self._data

    def get_ptr(self):
        return self._ptr

    def get_leftPtr(self):
        return self._leftPtr

    def get_rightPtr(self):
        return self._rightPtr

    def set_data(self, data):
        self._data = data

    def set_ptr(self, ptr):
        self._ptr = ptr

    def set_leftPtr(self, leftPtr):
        self._leftPtr = leftPtr

    def set_rightPtr(self, rightPtr):
        self._rightPtr = rightPtr

    def __str__(self):
        return "Data Value: " + self._data + " , Pointer Value: " + str(self._ptr)

class BST:
    def __init__(self, size):
        self._tree = [Node('', i + 1, -1, -1) for i in range(size - 1)]
        self._tree.append(Node('', -1, -1, -1))
        self._root = -1
        self._nextFree = 0

    def getFreeNode(self):
        if self._nextFree == -1:
            return 0
        else:
            temp = self._nextFree
            self._nextFree = self._tree[temp].get_ptr()
            self._tree[temp].set_ptr(0)
            return temp

    def returnNode(self, ptr):

        # begin: add to nextFree linked list
        node = self._tree[ptr]
        node.set_ptr(self._nextFree)
        self._nextFree = ptr
        # end: add to nextFree linked list

        # begin: 'reset' node
        node.set_data('')
        node.set_leftPtr(-1)
        node.set_rightPtr(-1)
        # end: 'reset' node

    def addNode(self, newItem):

        if self._nextFree == -1:
            return

        else:

            # begin: set data to free node
            free_pos = self.getFreeNode()
            free_node = self._tree[free_pos]
            free_node.set_data(newItem)
            # end: set data to free node

            # begin: assign free node to correct branch of BST
            if self._root == -1:
                self._root = free_pos

            else:

                # begin: traverse the tree until the free position is found
                def helper(curr, data):
                    curr_data = self._tree[curr].get_data()

                    if data > curr_data:
                        rightPtr = self._tree[curr].get_rightPtr()

                        # found it
                        if rightPtr == -1:
                            self._tree[curr].set_rightPtr(free_pos)

                        else:
                            helper(rightPtr, data)

                    else:
                        leftPtr = self._tree[curr].get_leftPtr()

                        # found it
                        if leftPtr == -1:
                            self._tree[curr].set_leftPtr(free_pos)

                        else:
                            helper(leftPtr, data)

                helper(self._root, newItem)
                # end: traverse the tree until the free position is found

            # end: assign free node to correct branch of BST

    def deleteRoot(self):

        if self._root == -1:
            return

        root_node = self._tree[self._root]

        # begin: simple cases
        if root_node.get_leftPtr() == -1 and root_node.get_rightPtr() == -1:
            self.returnNode(self._root)
            self._root = -1

        elif root_node.get_leftPtr() == -1 and root_node.get_rightPtr() != -1:
            temp = self._root
            self._root = root_node.get_rightPtr()
            self.returnNode(temp)

        elif root_node.get_rightPtr() == -1 and root_node.get_leftPtr() != -1:
            temp = self._root
            self._root = root_node.get_leftPtr()
            self.returnNode(temp)
        # end: simple cases

        # begin: have both left and right child
        else:

            # begin: find maximum of left subtree (and its parent)
            def findMax(root, prev):
                if self._tree[root].get_rightPtr() == -1:
                    return [root, prev]
                else:
                    return findMax(self._tree[root].get_rightPtr(), root)

            [left_max, parent] = findMax(self._tree[self._root].get_leftPtr(), None)
            # end: find maximum of left subtree (and its parent)

            # begin: set root to be maximum of left subtree
            self._tree[left_max].set_rightPtr(root_node.get_rightPtr())

            if parent:
                # successor is a right child

                # right child of parent <-- left child of successor
                self._tree[parent].set_rightPtr(self._tree[left_max].get_leftPtr())

                # left child of successor <-- left child of root
                self._tree[left_max].set_leftPtr(root_node.get_leftPtr())

            else:
                # successor is just the left child of root
                pass

            temp = self._root
            self._root = left_max
            # end: set root to be maximum of left subtree

            self.returnNode(temp)
        # end: have both left and right child

    def height(self):

        def helper(curr):
            if curr == -1:
                return -1
            else:
                return max(1 + helper(self._tree[curr].get_leftPtr()),\
                           1 + helper(self._tree[curr].get_rightPtr()))

        return helper(self._root)

    def childCount(self):

    # Returns the total number of nodes in the logical BST that has only 1 child.
    # If there is no node in the logical BST, it returns 0.

        def helper(curr):
            if self._root == -1:
                return 0

            elif curr.get_leftPtr() == -1 and curr.get_rightPtr() != -1:
                return 1

            elif curr.get_rightPtr() == -1 and curr.get_leftPtr() != -1:
                return 1

            elif curr.get_leftPtr() != -1 and curr.get_rightPtr() != -1:
                return helper(self._tree[curr.get_leftPtr()]) + \
                       helper(self._tree[curr.get_rightPtr()])

            else:
                return 0

        return helper(self._tree[self._root])

    def reverseTraversal(self):

        to_ret = []

        def helper(curr):

            nonlocal to_ret

            # right (biggest)
            if curr.get_rightPtr() != -1:
                helper(self._tree[curr.get_rightPtr()])

            # root
            to_ret.append(curr.get_data())

            # left (smallest)
            if curr.get_leftPtr() != -1:
                helper(self._tree[curr.get_leftPtr()])

        helper(self._tree[self._root])

        return to_ret

    def inOrderTraversal(self):

        if self._root == -1:
            return []

        to_ret = []

        def helper(curr):

            nonlocal to_ret

            # left (smallest)
            if curr.get_leftPtr() != -1:
                helper(self._tree[curr.get_leftPtr()])

            # root
            to_ret.append(curr.get_data())

            # right (biggest)
            if curr.get_rightPtr() != -1:
                helper(self._tree[curr.get_rightPtr()])

        helper(self._tree[self._root])

        return to_ret

    def preOrderTraversal(self):

        to_ret = []

        def helper(curr):

            nonlocal to_ret

            # root
            to_ret.append(curr.get_data())

            # left
            if curr.get_leftPtr() != -1:
                helper(self._tree[curr.get_leftPtr()])

            # right
            if curr.get_rightPtr() != -1:
                helper(self._tree[curr.get_rightPtr()])

        helper(self._tree[self._root])

        return to_ret

    def postOrderTraversal(self):

        to_ret = []

        def helper(curr):

            nonlocal to_ret

            # left
            if curr.get_leftPtr() != -1:
                helper(self._tree[curr.get_leftPtr()])

            # right
            if curr.get_rightPtr() != -1:
                helper(self._tree[curr.get_rightPtr()])

            # root
            to_ret.append(curr.get_data())


        helper(self._tree[self._root])

        return to_ret

    def displayArray(self):
        print("next free", self._nextFree)
        print('root', self._root)
        for i in range(len(self._tree)):
            print ("Slot Number "+ str(i) + " " + str(self._tree[i]) + \
                   ' leftPtr: ' + str(self._tree[i]._leftPtr) + \
                   ' rightPtr: ' + str(self._tree[i]._rightPtr))

def test1():
    BT = BST(7)
    BT.addNode("Dave")
    BT.addNode("Fred")
    BT.addNode("Ed")
    BT.addNode("Greg")
    BT.addNode("Bob")
    BT.addNode("Cid")
    BT.addNode("John")
    BT.addNode("Ali") #not added because it is the 8th node
    return BT.inOrderTraversal() == ['Bob', 'Cid', 'Dave', 'Ed', 'Fred', 'Greg', 'John'] and BT.height() == 3


def test2():
    BT = BST(7)
    BT.addNode("Dave")
    BT.addNode("Fred")
    BT.addNode("Ed")
    BT.addNode("Greg")
    BT.addNode("Bob")
    BT.addNode("Cid")
    BT.addNode("Ali")
    #Call for deleteRoot 8 times
    BT.deleteRoot()
    BT.deleteRoot()
    BT.deleteRoot()
    BT.deleteRoot()
    BT.deleteRoot()
    BT.deleteRoot()
    a = BT.height() # a = 0 because BST has only 1 node
    BT.deleteRoot()
    b = BT.height() # -1 No BST no height
    #BST is empty, deleteRoot() does nothing
    return BT.inOrderTraversal() == [] and a == 0 and b == -1

def test3():
    BT = BST(7)
    BT.addNode("Dave")
    BT.addNode("Fred")
    BT.addNode("Ed")
    BT.addNode("Greg")
    BT.addNode("Bob")
    BT.addNode("Cid")
    BT.addNode("Ali")
    #Call for deleteRoot 8 times
    BT.deleteRoot()
    BT.deleteRoot()
    BT.deleteRoot()
    BT.deleteRoot()
    BT.deleteRoot()
    BT.deleteRoot()
    BT.deleteRoot()
    BT.deleteRoot()
    #re-insert the items to ensure BST work again.
    BT.addNode("Dave")
    BT.addNode("Fred")
    BT.addNode("Ed")
    BT.addNode("Greg")
    BT.addNode("Bob")
    BT.addNode("Cid")
    BT.addNode("Ali")
    return BT.inOrderTraversal() == ['Ali', 'Bob', 'Cid', 'Dave', 'Ed', 'Fred', 'Greg']

print(test1())
print(test2())
print(test3())