from random import random


class Node:
    left = None
    right = None
    key = None
    val = None

    def __init__(self, key, val):
        self.key = key
        self.val = val


class BST:
    root = None

    def _size(self, node):
        if node:
            return 1 + self._size(node.left) + self._size(node.right)
        return 0

    def size(self):
        return self._size(self.root)

    def depth(self):
        return self._depth(self.root)

    def _depth(self, node):
        if node:
            return 1 + max(self._depth(node.left),
                           self._depth(node.right))
        return 0

    def getMin1(self):
        if self.root is None:
            return None
        return self._getMin1(self.root)

    def _getMin1(self, node):
        if node.left:
            return self._getMin1(node.left)
        return node.val

    def getMin2(self):
        if self.root is None:
            return None
        node = self.root
        while node.left is not None:
            node = node.left
        return node.val

    def put(self, key, val):
        self.root = self._put(self.root, key, val)

    def _put(self, node, key, val):
        if node:
            if key == node.key:
                node.val = val
            if key < node.key:
                node.left = self._put(node.left, key, val)
            else:
                node.right = self._put(node.right, key, val)
            return node
        return Node(key, val)

    def put2(self, key, val):
        if self.root is None:
            self.root = Node(key, val)
            return
        parent = None
        current = self.root
        while current is not None:
            if key == current.key:
                current.val = val
                return
            parent = current
            if key < current.key:
                current = current.left
            else:
                current = current.right
        if key < parent.key:
            parent.left = Node(key, val)
        else:
            parent.right = Node(key, val)

    def get(self, key):
        return self._get(self.root, key)

    def _get(self, node, key):
        if node:
            if key == node.key:
                return node.val
            if key < node.key:
                return self._get(node.left, key)
            else:
                return self._get(node.right, key)

    def get2(self, key):
        node = self.root
        while node is not None:
            if node.key == key:
                return node.val
            if key < node.key:
                node = node.left
            else:
                node = node.right
        return None

    def remove(self, key):
        val = self.get(key)
        if val:
            self.root = self._remove(self.root, key)

    def _remove(self, node, key):
        if key == node.key:
            if node.left is None:
                return node.right
            if node.right is None:
                return node.left
            todelete = self._least(node.right)
            node.key = todelete.key
            node.val = todelete.val
            self._remove(node.right, todelete.key)
            return node
        if key < node.key:
            node.left = self._remove(node.left, key)
        else:
            node.right = self._remove(node.right, key)
        return node

    def _least(self, node):
        if node.left:
            return self._least(node.left)
        return node

    def clear(self):
        self.root = None

    def inorder(self):
        result = list()
        self._inorder(result, self.root)
        return result

    def _inorder(self, result, node):
        if node:
            self._inorder(result, node.left)
            result.append(node.key)
            self._inorder(result, node.right)

    def preorder(self):
        result = list()
        self._preorder(result, self.root)
        return result

    def _preorder(self, result, node):
        if node:
            result.append(node.key)
            self._preorder(result, node.left)
            self._preorder(result, node.right)

    def postorder(self):
        result = list()
        self._postorder(result, self.root)
        return result

    def _postorder(self, result, node):
        if node:
            self._postorder(result, node.left)
            self._postorder(result, node.right)
            result.append(node.key)


def smoke_test():
    dict = BST()
    print("uno: ", dict.get("uno"))
    dict.put("uno", "1")
    print("uno: ", dict.get("uno"))
    dict.put("dos", "2")
    dict.put("tres", "3")
    print("dos: ", dict.get("dos"))
    print("len: ", dict.size())
    dict.remove("uno")
    print("uno: ", dict.get("uno"))
    print("len: ", dict.size())
    dict.remove("xxx")
    print("dos: ", dict.get("dos"))
    print("len: ", dict.size())
    dict.remove("dos")
    print("dos: ", dict.get("dos"))
    print("len: ", dict.size())
    dict.remove("tres")
    print("tres: ", dict.get("tres"))
    print("len: ", dict.size())


def depth_test():
    hist = [0] * 100
    for i in range(1000):
        bst = BST()
        for j in range(100):
            r = (int)(10000 * random())
            bst.put(r, r)
        depth = bst.depth()
        hist[depth] += 1
    print(hist)


def example_test():
    tree = BST()
    tree.put(15, 15)
    tree.put(8, 8)
    tree.put(24, 24)
    tree.put(5, 5)
    tree.put(19, 19)
    tree.put(12, 12)
    tree.put(9, 9)
    tree.put(30, 30)
    tree.put(28, 28)
    tree.put(17, 17)
    tree.put(20, 20)

    assert(11 == tree.size())
    assert(4 == tree.depth())

    assert([15, 8, 5, 12, 9, 24, 19, 17, 20, 30, 28] == tree.preorder())
    assert([5, 8, 9, 12, 15, 17, 19, 20, 24, 28, 30] == tree.inorder())
    assert([5, 9, 12, 8, 17, 20, 19, 28, 30, 24, 15] == tree.postorder())

    tree.remove(5)
    tree.remove(8)
    tree.remove(24)
    tree.remove(15)
    tree.remove(20)

    assert(6 == tree.size())
    assert(3 == tree.depth())

    assert([17, 12, 9, 28, 19, 30] == tree.preorder())
    assert([9, 12, 17, 19, 28, 30] == tree.inorder())
    assert([9, 12, 19, 30, 28, 17] == tree.postorder())

if __name__ == '__main__':
    # smoke_test()
    # depth_test()
    example_test()