import random
import math

class BST:
    def __init__(self):
        '''creates an empty BST, consisting in a dummy leaf'''
        self.key = None
        self.info = None
        self.left = None
        self.right = None
#        self.num_elems = 0  # this can be updated during insertions and deletions
                             # in order to speed-up size() method
        
    def insert(self, key, info):
        '''creates a new node containing key in the BST.
If key already exists, the previous info value is replaced by the current info and returns False, otherwise a new node (with two dummy leaves) is added and returns True'''
        if self.key is None:
            self.key = key
            self.info = info
            self.left = BST()
            self.right = BST()
            return True
        elif key < self.key:
            if self.left.insert(key, info):
                return True
            else:
                return False
        elif key > self.key:
            if self.right.insert(key, info):
                return True
            else:
                return False
        else: # key == self.key
            self.info = info
            return False

    def pre_order_visit(self):
        '''returns a list containing items in the BST according to an in-order visit'''
        if self.key is None:
            return []
        res = [(self.key, self.info)]
        res.extend(self.left.pre_order_visit())
        res.extend(self.right.pre_order_visit())
        return res
        
    def in_order_visit(self):
        '''returns a list containing items in the BST according to an in-order visit'''
        if self.key is None:
            return []
        res = self.left.in_order_visit()
        res.append((self.key, self.info))
        res.extend(self.right.in_order_visit())
        return res
        
    def post_order_visit(self):
        '''returns a list containing items in the BST according to an in-order visit'''
        if self.key is None:
            return []
        res = self.left.post_order_visit()
        res.extend(self.right.post_order_visit())
        res.append((self.key, self.info))
        return res
        
    def search(self, key):
        '''returns the value associated to key, if it exists.
Returns None if key does not exist'''
        if self.key is None: # search terminated in a dummy node
            return None
        elif key == self.key:
            return self.info
        elif key < self.key:
            return self.left.search(key)
        else:
            return self.right.search(key)

    def minimum(self):
        '''returns the pair key, info for the minimum key in the BST.
Returns None if the tree is empty'''
        # if the root has non left child, the root is the minimum
        # otherwise look in the left subtree
        
    def maximum(self):
        '''returns the pair key, info for the maximum key in the BST.
Returns None if the tree is empty'''
        # similar to minimum
                
    def height(self):
        if self.key is None:
            return 0
        else:
            return 1 + max(self.left.height(), self.right.height())

    def size(self):
        '''returns the number of elements in the tree'''
        # to be implemented recursively---see height()

    def print_tree(self):
        '''prints a parenthesized representation of the tree, similar to an in-order visit'''
        if self.key is not None:
            print("(", end="")
            self.left.print_tree()
            print(f' {self.key} ', end="")
            self.right.print_tree()
            print(")", end="")



a = BST()

items = [[23, 230], [12, 120], [44, 440], [11, 110], [10, 100], [13, 130], [40, 400], [45, 450], [42, 420]]
for x in items:
    a.insert(*x)

a.print_tree()

# print(f'size = {a.size()}')
print("pre-order:", a.pre_order_visit())
print("in-order:", a.in_order_visit())
print("post-order:", a.post_order_visit())

# l = a.in_order_visit()
# for x in l:
#     print(f'key {x}: rank {a.rank(x[0])}')

# print(f'minimum: {a.minimum()}')
# print(f'maximum: {a.maximum()}')
# 
# print("height:", a.height())
# delete(22)
# delete(30)
# delete(45)
# delete(44)
# delete(23)
# delete(12)
# for x in items:
#     print(f'key {x[0]}: rank {a.rank(x[0])}')
# 
# for i in range(a.size()):
#     print(a.get_kth_item(i))
#     
# delete(10)
# delete(11)
# delete(40)
# delete(13)
# delete(42)
# 
# num_keys = 10000000
# max_val = 10 * num_keys
# b = BST()
# print(f'{"size":11s} {"h":4s}  {"log":4s}')
# for i in range(num_keys):
#     x = random.randint(1, max_val)
#     b.insert(x, 111) # inserts (random_key, 111)
#     size = b.size()
#     if size in [2**k-1 for k in range(1,math.ceil(math.log2(num_keys)))]:
#         print(f'{size:9d} {b.height():4d}   {int(math.log2(size+1)):4d}')
# print(f"built BST with {b.size()} keys. Height = {b.height()}")