class TreeNode :
    #constructor, Time O(1) Space O(1)
    def __init__(self) :      
        self.left = None
        self.right = None 
   
    #Override, Time O(1), Space O(1)
    def __str__(self):
    	return str(self.data)

class BinarySearchTree :
    #constructor, Time O(1) Space O(1)
    def __init__(self) :
        self.root = None
	
	#Insert a node based on value, Iteration, Time O(h) Space O(1), h is height of tree
    def insert(self, value) :
        newNode = TreeNode()    
        newNode.data = value;		
        if self.root == None:               
            self.root = newNode
            return
        curr = self.root       
        prev = None
        while (True) :
            prev = curr
            if value < curr.data :
                curr = curr.left
                if (curr == None) :                
                    prev.left = newNode
                    return			
            else :
                curr = curr.right
                if curr == None :           
                    prev.right = newNode
                    return
					
	#Delete node by key, Iteration, Time O(h), Space O(1)
    def delete(self, key) :
        if self.root == None :
            return None
        if self.root.data == key :
            self.root = self.getSuccessor(self.root)     	
            return self.root
        curr = self.root;     
        while True : 
            if key > curr.data:
                if curr.right == None or curr.right.data == key :
                    curr.right = self.getSuccessor(curr.right)
                    break
                curr = curr.right
            else :
                if curr.left == None or curr.left.data == key:
                    curr.left = self.getSuccessor(curr.left)
                    break           
                curr = curr.left
        return self.root

    #Delete node, return next successor, Time O(h), Space O(1)
    def getSuccessor(self, node) :
        if node == None: 
        	return None
        if node.right == None : 
        	return node.left
        curr = node.right
        while curr.left != None: #find the left-most node
        	curr = curr.left
        curr.left = node.left
        return node.right
    
    #Depth first search, recursion, Time O(h), Space O(h)
    def searchDFS(self, key) :
        return self.dfsHelper(self.root, key);		
		
    #Search recursion helper, Time O(h), Space O(h)
    def dfsHelper(self, node, key) :
        if node == None: 
            return None      
        if node.data == key: 
            return node
        return self.dfsHelper(node.right, key) if key> node.data else self.dfsHelper(node.left, key)
    
    #Iteration, Time O(h), Space O(1)
    def searchBFS(self, key) :                           
        curr = self.root             
        while curr!= None :
            if curr.data == key:
                return curr
            elif key < curr.data:
                curr = curr.left
            else :                           
                curr = curr.right              
        return curr                    
	
	#Inorder traversal, Time O(n), Space O(n), n is number of nodes in trees
    def inorder(self) :
        list = []
        self.inorderRec(self.root, list)
        return list
    
	#Inorder recursion helper, Time O(n), Space O(h)
    def inorderRec(self, node, list) :
        if node == None: 
            return
        self.inorderRec(node.left, list)
        list.append(node.data)
        self.inorderRec(node.right, list)
	
	
	#Preorder traversal, Time O(n), Space O(n) 
    def preorder(self) :
        list = []
        self.preorderRec(self.root, list)
        return list
    
	#Preorder recursion helper, Time O(n), Space O(h) 
    def preorderRec(self, node, list) :
        if node == None:
            return
        list.append(node.data)
        self.preorderRec(node.left, list)
        self.preorderRec(node.right, list)		
		
	#Postorder traversal, Time O(n), Space O(n) 
    def postorder(self) :
        list = []
        self.postorderRec(self.root, list)
        return list
	
	#Postorder recursion helper, Time O(n), Space O(h) 
    def postorderRec(self, node, list) :
        if node == None: 
            return
        self.postorderRec(node.left, list)
        self.postorderRec(node.right, list)
        list.append(node.data);		

	#Level order traversal, Iteration, Time O(n), Space O(n)
    def levelOrder(self) :
        list = []
        if self.root is None:
            return list
        queue = [self.root] 
        while (len(queue) >0):
            curr = queue.pop(0)
            list.append(curr.data)                     
            if curr.left is not None:
                queue.append(curr.left)
            if curr.right is not None:
                queue.append(curr.right)
        return list

tree = BinarySearchTree()
tree.insert(50)
tree.insert(12)
tree.insert(25)
tree.insert(75)
tree.insert(37)
tree.insert(22)
tree.insert(43)
print("The root: " + str(tree.root.data)); 

print("Preorder: " + str(tree.preorder()))
print("Inorder: " + str(tree.inorder()))
print("Postorder: " + str(tree.postorder()))
print("Level order: " + str(tree.levelOrder()))

#search
key = 25
node = tree.searchDFS(key)
print("\nDFS Search " + str(key) + ", node data: " + str(node))

key = 12
node = tree.searchBFS(key)
print("BFS Search " + str(key) + ", node data: " + str(node))

#Delete 
key = 12	
tree.root  = tree.delete(key);   
print("\nAfter delete " + str(key))
print("The root: " + str(tree.root.data)); 
print("Preorder: " + str(tree.preorder()))
print("Inorder: " + str(tree.inorder()))
print("Postorder: " + str(tree.postorder())) 
print("level order: " + str(tree.levelOrder()))	
node = tree.searchDFS(key)
print("DFS Search " + str(key) + ", node data: " + str(node))