class TreeNode(object):

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

    def __str__(self):
        return str(self.item)

from TreeNode import TreeNode


class BST(object):

    #------------------------------------------------------------

    def __init__(self):

        """create empty binary search tree
        post: empty tree created"""

        self.root = None

    def delete(self, item):

        """remove item from binary search tree
        post: item is removed from the tree"""

        self.root = self._subtreeDelete(self.root, item)

    #------------------------------------------------------------

    def _subtreeDelete(self, root, item):

        if root is None:   # Empty tree, nothing to do
            return None
        if item < root.item:                             # modify left
            root.left = self._subtreeDelete(root.left, item)
        elif item > root.item:                           # modify right
            root.right = self._subtreeDelete(root.right, item)
        else:                                            # delete root
            if root.left is None:                        # promote right subtree
                root =  root.right
            elif root.right is None:                     # promote left subtree
                root = root.left
            else:
                # root node can't be deleted, overwrite it with max of
                #    left subtree and delete max node from the subtree
                root.item, root.left = self._subtreeDelMax(root.left)
        return root

 def _subtreeDelMax(self, root):

        if root.right is None:           # root is the max
            return root.item, root.left  # return max and promote left subtree
        else:
            # max is in right subtree, recursively find and delete it
            maxVal, root.right = self._subtreeDelMax(root.right)
            return maxVal, root

 def treeSize(self, root, size = 0):

        if root is None:
            return -1

        if root is not None:
            self.size += 1
            if root.left is not None:
                self.treeSize(root.left, size)
            if root.right is not None:
                self.treeSize(root.right, size)
        return self.size