Arsenal for Binary Search Tree Adventures

binarySearchTree.py

class Node():
    """
    Basic component of a Tree is a Node
    """

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree():
    """
    Binary Tree Implementation using Node
    """

    def __init__(self):
        self.root = None


    def create(self, value):
        """
        Create the Binary Tree 
        Lower values go to left
        Bigger values go to right
        """
        if not self.root:
            self.root = Node(value)
            return
        else:
            current = self.root
        
        while True:
            if value < current.value:
                if current.left:
                    current = current.left
                else:
                    current.left = Node(value)
                    break
            elif value > current.value:
                if current.right:
                    current = current.right
                else:
                    current.right = Node(value)
                    break
            else:
                print("Already exists")
                break

    def preOrderTraversal(self, root):
        """
        Root, Left, Right 
        """
        if root:
            print(root.value, end=" ")
            self.preOrderTraversal(root.left)
            self.preOrderTraversal(root.right)

    def inOrderTraversal(self, root):
        """
        Left, Root, Right
        """
        if root:
            self.inOrderTraversal(root.left)
            print(root.value, end=" ")
            self.inOrderTraversal(root.right)

    def postOrderTraversal(self, root):
        """
        Left, Right, Root
        """
        if root:
            self.postOrderTraversal(root.left)
            self.postOrderTraversal(root.right)
            print(root.value, end=" ")

    def levelOrderTraversal(self, startPosition):
        """
        Traverse in levels
        """
        queueList = []
        queueList.append(startPosition)
        
        while len(queueList)>0:
            print(queueList[0].value, end = " ")
            node = queueList.pop(0)
            
            if node.left:
                queueList.append(node.left)
            if node.right:
                queueList.append(node.right)

    def reverseLevelOrderTraversal(self, startPosition):
        """
        Reverse travel in levels 
        """
        queueList = []
        queueList.append(startPosition)
        result = []
        
        while len(queueList)>0:
            node = queueList.pop(0)
            if node.right:
                queueList.append(node.right)
            if node.left:
                queueList.append(node.left)
 
            result.append(node.value)
        
        while result:
            print(result.pop(), end = " ")


    def traversal(self, mode="pre"):
        if mode == "pre":
            self.preOrderTraversal(self.root)
        elif mode == "in":
            self.inOrderTraversal(self.root)
        elif mode == "post":
            self.postOrderTraversal(self.root)
        elif mode == "level":
            self.levelOrderTraversal(startPosition = self.root)
        elif mode == "revlevel":
            self.reverseLevelOrderTraversal(startPosition = self.root)
        else:
            print("Invalid mode of traversal, Try pre, in, post, level or revlevel")

    def height(self, root=None):
        """
        Find height of a Node
        Height is number of edges from that node to the farthest leaf node
        """
        if not root:
            root = self.root
        
        def _height(root):
            if not root:
                return -1
            leftHeight = _height(root.left)
            rightHeight = _height(root.right)
            return 1 + max(leftHeight, rightHeight)

        print(_height(root))

    def size(self):
        """
        No. of nodes in a tree
        """
        if not self.root:
            return 0

        treeSize = 1
        queueList = []
        queueList.append(self.root)
        
        while len(queueList)>0:
            node = queueList.pop(0)
            if node.left:
                treeSize += 1
                queueList.append(node.left)
            if node.right:
                treeSize += 1
                queueList.append(node.right)
        print(treeSize)

    def find(self, value = None, startNode = None):
        if not value:
            return False
        if not startNode:
            startNode = self.root

        def _find(value, startNode):
            if value == startNode.value:
                return True
            elif value < startNode.value and startNode.left:
                return _find(value, startNode.left)
            elif value > startNode.value and startNode.right:
                return _find(value, startNode.right)
            else:
                return False
        return _find(value, startNode)

    def _minValNode(self, node):
        if node is None:
            return None
        while node.left:
            node = node.left
        return node   

    def _deleteNode(self, root, value):

        if root is None:
            return 

        if root.value == value:
            if root.left is None:
                return root.right
            if root.right is None:
                return root.left
            successor = self._minValNode(root.right)
            root.value = successor.value
            root.right = self._deleteNode(root.right, successor.value)
        elif value < root.value:
            root.left = self._deleteNode(root.left, value)
        else:
            root.right = self._deleteNode(root.right, value)
        return root

    def deleteValue(self, value=None):
        
        if not value:
            return False
        
        current = self.root
        current = self._deleteNode(current, value)



# if __name__ == "__main__":
#     input_array = [1, 2, 5, 3, 6, 4]
#     binarySearchTree = BinarySearchTree()

#     for val in input_array:
#         binarySearchTree.create(val)

#     binarySearchTree.traversal("pre")
#     print("\n")
#     binarySearchTree.traversal("in")
#     print("\n")
#     binarySearchTree.traversal("post")
#     print("\n")
#     binarySearchTree.traversal("level")
#     print("\n")
#     binarySearchTree.traversal("revlevel")
#     print("\n")
#     binarySearchTree.height()
#     print("\n")
#     binarySearchTree.size()
#     print("\n")
#     binarySearchTree.deleteValue(4)
#     binarySearchTree.traversal("in")
#     print("\n")
#     print(binarySearchTree.find())