Katbin

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

    def insert(self, val):
        """For inserting the value in the Tree"""
        if self.val == val:
            return False  # A BST cannot contain duplicate data

        elif val < self.val:
            """Values less than the root data are placed to the left of the root"""
            if self.left_child:
                return self.left_child.insert(val)
            else:
                self.left_child = Node(val)
                return True

        else:
            """Values greater than the root data are placed to the right of the root"""
            if self.right_child:
                return self.right_child.insert(val)
            else:
                self.right_child = Node(val)
                return True

    def min_node(self, node):
        current = node

        # Find the leftmost leaf
        while current.left_child is not None:
            current = current.left_child

        return current

    def max_node(self, node):
        current = node

        # Find the leftmost leaf
        while current.right_child is not None:
            current = current.right_child

        return current

    def delete(self, val, root):
        """For deleting the node"""
        if self is None:
            return None

        # If current node's data is less than that of root node,
        # then only search in left subtree, otherwise search in right subtree
        if val < self.val:
            self.left_child = self.left_child.delete(val, root)
        elif val > self.val:
            self.right_child = self.right_child.delete(val, root)
        else:
            # Deleting node with one child
            if self.left_child is None:

                if self == root:
                    temp = self.min_node(self.right_child)
                    self.val = temp.val
                    self.right_child = self.right_child.delete(temp.val, root)

                temp = self.right_child
                self = None
                return temp
            elif self.right_child is None:

                if self == root:
                    temp = self.max_node(self.left_child)
                    self.val = temp.val
                    self.left_child = self.left_child.delete(temp.val, root)

                temp = self.left_child
                self = None
                return temp

            # Deleting node with two children
            # First get the in-order successor
            temp = self.min_node(self.right_child)
            self.val = temp.val
            self.right_child = self.right_child.delete(temp.val, root)

        return self

    def find(self, val):
        """This function checks whether the specified val is in tree or not"""
        if val == self.val:
            return True
        elif val < self.val:
            if self.left_child:
                return self.left_child.find(val)
            else:
                return False
        else:
            if self.right_child:
                return self.right_child.find(val)
            else:
                return False

    def preorder(self):
        """For preorder traversal of the BST"""
        if self:
            print(str(self.val), end=" ")
            if self.left_child:
                self.left_child.preorder()
            if self.right_child:
                self.right_child.preorder()

    def inorder(self):
        """For Inorder traversal of the BST"""
        if self:
            if self.left_child:
                self.left_child.inorder()
            print(str(self.val), end=" ")
            if self.right_child:
                self.right_child.inorder()

    def postorder(self):
        """For postorder traversal of the BST"""
        if self:
            if self.left_child:
                self.left_child.postorder()
            if self.right_child:
                self.right_child.postorder()
            print(str(self.val), end=" ")


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

    def insert(self, val):
        if self.root:
            return self.root.insert(val)
        else:
            self.root = Node(val)
            return True

    def delete(self, val):
        if self.root is not None:
            return self.root.delete(val, self.root)

    def find(self, val):
        if self.root:
            return self.root.find(val)
        else:
            return False

    def preorder(self):
        if self.root is not None:
            print()
            print("Preorder: ")
            self.root.preorder()

    def inorder(self):
        print()
        if self.root is not None:
            print("Inorder: ")
            self.root.inorder()

    def postorder(self):
        print()
        if self.root is not None:
            print("Postorder: ")
            self.root.postorder()


if __name__ == "__main__":
    tree = Tree()
    tree.insert(11)
    tree.insert(9)
    tree.insert(6)
    tree.insert(3)
    tree.insert(17)
    tree.insert(5)
    tree.insert(4)
    tree.insert(19)
    tree.insert(12)
    print(tree.find(13))
    print(tree.find(5))
    """ The following tree is generated:
                    11
                 /     \
               6        9
              /           \
            3              17
             \             /  \
              5          12    19
             /
            4
    """

    tree.preorder()
    tree.inorder()
    tree.postorder()
    print("\n\nAfter deleting 19")
    tree.delete(19)
    tree.inorder()
    tree.preorder()
    print("\n\nAfter deleting 12")
    tree.delete(12)
    tree.inorder()
    tree.preorder()