class Stack:
    def __init__(self):
        self.data = []
        
    def is_empty(self):
        return len(self.data)==0
        
    def push(self,e):
            self.data.append(e) 

    def top_element(self):
        if not self.is_empty():
            return 1,self.data[-1]
        else:
            return 0,None
            
    def pop(self):
        if not self.is_empty():
            x=self.data[-1]
            self.data.pop()
            return 1,x
        else:
            return 0,None
            
    def show(self):
        for x in self.data:
            print(x,end="<-")
        print()    
        
class Queue:
    def __init__(self):
        self.data=[]

    def __len__(self):
        return len(self.data)
        
    def is_empty(self):
        return len(self.data)==0

  
    def push(self,obj):
        self.data.append(obj)
        
    def pop(self):
        if not self.is_empty():
            y=self.data[0]
            self.data.pop(0)
            return 1,y
        else:
            return 0,None

    def front_element(self):
        if not self.is_empty():
            return 1,self.data[0]
        else:
            return 0,None

    def show(self):
        if not self.is_empty():
            for x in self.data:
                print(x,end='->')
            print()
        else:
            print('Queue is empty')
class BST:
    class BSTNode:
        class Element:
            def __init__(self,key,value):
                self.Key=key
                self.Value=value
        def __init__(self,key,value,left=None,right=None):
            self.LChild=left
            self.RChild=right
            self.Data=self.Element(key,value)
            
    def __init__(self):
        self.root=None
        
    def is_empty(self):
        return self.root==None
        
    def inorder_help(self,node):
        if node!=None:
            self.inorder_help(node.LChild)
            print(node.Data.Key,end='->')
            self.inorder_help(node.RChild)
    def inorder_traversal(self):
            self.inorder_help(self.root)
        
    def preorder_help(self,node):
        if node!=None:
            print(node.Data.Key,end='->')
            self.preorder_help(node.LChild)
            self.preorder_help(node.RChild)
    def preorder_traversal(self):
            self.preorder_help(self.root)
    
    def inorder_search(self,node,key):
        if node==None:
            return None
        v=self.inorder_search(node.LChild,key)
        if v:
            return v
        if node.Data.key==key:
                return node
        v=self.inorder_search(node.RChild,key)
        if v:
            return v
    
    def level_order_traversal(self):
        q=Queue()
        q.push(self.root)
        while not q.is_empty():
            flag,y=q.pop()
            print(y.Data.Key,end='-')
            if y.LChild!=None:
                q.push(y.LChild)
            if y.RChild!=None:
                q.push(y.RChild)
                
    def recursive_size_help(self,node):
         if node==None:
             return 0
         else:
            left_size=self.recursive_size_help(node.LChild)
            right_size=self.recursive_size_help(node.RChild) 
            return left_size+right_size+1
    def recursive_size(self):
            return self.recursive_size_help(self.root)

    def iterative_size(self):
        if self.root is None:
            return 0
        stack = Stack()
        stack.push(self.root)
        size = 1
        while not stack.is_empty():
            node = stack.pop()[1]
            if node.LChild:
                size += 1
                stack.push(node.LChild)
            if node.RChild:
                size += 1
                stack.push(node.RChild)
        return size

    def leaf_size_help(self,node):
         if node==None:
             return 0
         elif node.LChild==None and node.RChild==None:
             return 1   
         elif node.LChild!=None and node.RChild==None:
                 left_size=self.leaf_size_help(node.LChild)
                 return left_size
         elif node.RChild!=None and node.LChild==None:
                 right_size=self.leaf_size_help(node.RChild)
                 return right_size
         else:
             left_size=self.leaf_size_help(node.LChild)
             right_size=self.leaf_size_help(node.RChild)
             return right_size+left_size
    def leaf_size(self):
            return self.leaf_size_help(self.root)
        
    def two_degree_nodes_size_help(self,node):
         if node==None:
             return 0
         elif node.LChild!=None and node.RChild!=None:
             left_size=self.two_degree_nodes_size_help(node.LChild)
             right_size=self.two_degree_nodes_size_help(node.RChild)
             return left_size+right_size+1   
         elif node.LChild!=None:
                 left_size=self.two_degree_nodes_size_help(node.LChild)
                 return left_size
         elif node.RChild!=None:
                 right_size=self.two_degree_nodes_size_help(node.RChild)
                 return right_size
         else:
             return 0
    def two_degree_nodes_size(self):
            return self.two_degree_nodes_size_help(self.root)
        
    def one_degree_nodes_size_help(self,node):
         if node==None:
             return 0
         elif node.LChild!=None and node.RChild!=None:
             left_size=self.one_degree_nodes_size_help(node.LChild)
             right_size=self.one_degree_nodes_size_help(node.RChild)
             return left_size+right_size   
         elif node.LChild!=None:
                 left_size=self.one_degree_nodes_size_help(node.LChild)
                 return left_size+1
         elif node.RChild!=None:
                 right_size=self.one_degree_nodes_size_help(node.RChild)
                 return right_size+1
         else:
             return 0
    def one_degree_nodes_size(self):
            return self.one_degree_nodes_size_help(self.root)

    def height_help(self,node):
        if node==None:
             return 0
        else:
            left_height=self.height_help(node.LChild)
            right_height=self.height_help(node.RChild) 
            return max(left_height,right_height)+1
    def height(self):
            return self.height_help(self.root)

    # Recursive function to find level of a Node with Data.Key=key in a binary search tree
    def level_help(self,node, key, lev):
        if node is None:
            return 0
        if node.Data.Key == key:
            return lev
        # return level if Node is present in left subtree
        le = self.level_help(node.LChild, key, lev + 1)
        if le != 0:
            return le
        # else: search in right subtree
        return self.level_help(node.RChild, key, lev + 1)
        
    def level(self, key):
        return self.level_help(self.root,key, 0)


    def insert_node_help(self,node,key,value):
        if node is None:
            # print(None,end=' ')
            return self.BSTNode(key,value)
        if node.Data.Key == key:
            # print('==',end=' ')
            return node
        if node.Data.Key < key:
            # print('<',end=' ')
            node.RChild = self.insert_node_help(node.RChild, key,value)
        else:
            # print('>',end=' ')
            node.LChild = self.insert_node_help(node.LChild, key,value)
        return node
    def insert_node(self,key,value):
        node=self.root
        self.root=self.insert_node_help(node,key,value)
        
    #find node with min key in the right
    def get_successor(self,curr):
        curr = curr.RChild
        while curr is not None and curr.LChild is not None:
            curr = curr.LChild
        return curr

    # This function deletes a given key x from the
    # given BST and returns the modified root of the 
    # BST (if it is modified).
    def del_node_help(self,node, key):
        # Base case
        if node is None:
            return None
        # If key to be searched is in a subtree
        if node.Data.Key > key:
            node.LChild = self.del_node_help(node.LChild, key) # the root address of new left subtree
        elif node.Data.Key < key:
            node.RChild = self.del_node_help(node.RChild, key) # the root address of new right subtree
        else:
            # If root matches with the given key
            # Cases when root has 0 children or 
            # only right child
            if node.LChild is None:
                return node.RChild
            # When root has only left child
            if node.RChild is None:
                return node.LChild
            # When both children are present
            succ = self.get_successor(node)
            node.Data.Key = succ.Data.Key
            node.Data.value=succ.Data.value
            node.RChild = self.del_node_help(node.RChild, succ.Data.Key)
        return node
    def del_node(self,key):
        self.root=self.del_node_help(self.root, key)

#==========================================================================#        
lst1=[(10,'A'),(20,'B'),(15,'C'),(25,'D'), (8,'E'),(6,'F'), (9,'G'),(12,'H'), (17,'I')]
bst1=BST()

for i in range(len(lst1)):
    bst1.insert_node(lst1[i][0],lst1[i][1])
    
print('inorder traversal:',end=' ')
bst1.inorder_traversal()

print('\npreorder traversal:',end=' ')
bst1.preorder_traversal()
print()
# print(bst1.root.Data.Key)

print('#Nodes(recursive size):',bst1.recursive_size())
print('#Nodes(iterative size):',bst1.iterative_size())
print('Height of BST:',bst1.height())
print('# leaves:',bst1.leaf_size())
print('# two_degree_nodes:',bst1.two_degree_nodes_size())
print('# one_degree_nodes:',bst1.one_degree_nodes_size())
key=12
print('level of a node with key='+str(key)+':',bst1.level(key))

key=9
bst1.del_node(key)
print('\npreorder traversal after deleting node with key='+str(key)+':',end=' ')
bst1.preorder_traversal()
print()