class TreeNode :

    #Constructor, TreeNode with a parent reference, Time O(1) Space O(1)
    def __init__(self) :      
        self.left = None
        self.right = None
        self.parent = None; 
   
    #Override, Time O(1), Space O(1)
    def __str__(self):
    	return str(self.data)

class BinarySearchTreeWithParent :

    #Constructor, Time O(1) Space O(1)
    def __init__(self) :
        self.root = None

	#Insert with parent pointer, 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       
        parent = None
        while True :
            parent = curr
            if value < curr.data: 
                curr = curr.left
                if curr == None:                
                    parent.left = newNode
                    newNode.parent = parent
                    return				
            else :
                curr = curr.right 
                if curr == None:                 
                    parent.right = newNode
                    newNode.parent =parent
                    return									
	
	#Delete with parent pointer, Iteration, Time O(h) Space O(1)
    def delete(self, key) :
        if self.root == None :
        	return None
        if self.root.data == key: #delete root
        	self.root = self.deleteNode(self.root) #reset the root
        	self.root.parent = None
        	return self.root
        curr = self.root     
        while True :
            if key > curr.data :
                if curr.right == None :
                	break
                elif curr.right.data == key:
                    oldParent = curr.right.parent
                    curr.right = self.deleteNode(curr.right)
                    if curr.right != None:
                    	curr.right.parent = oldParent
                    break
                curr = curr.right
            else :
                if curr.left == None:
                	break
                elif curr.left.data == key : 
                    oldParent = curr.right.parent
                    curr.left = self.deleteNode(curr.left)
                    if curr.left != None:
                    	curr.left.parent = oldParent
                    break     
                curr = curr.left
        return self.root
    
    #Delete node, Time O(h), Space O(1)
    def deleteNode(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 # put the original left under left most, 
        if node.left != None:
        	node.left.parent = curr # link the new far left part to old far 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                    
	
	#In-order traversal, Recursion, Time O(n), Space O(n), n is number of node in treee
    def inOrder(self) :
        list = []
        self.inHelper(self.root, list)
        return list
    
	#In-order recursion helper, Time O(n), Space O(h) 
    def inHelper(self, node, list) :
        if node == None: 
            return
        self.inHelper(node.left, list)
        list.append(node.data)
        self.inHelper(node.right, list)
	
	
	#Pre-order traversal, recursion, Time O(n), Space O(n) 
    def preOrder(self) :
        list = []
        self.preHelper(self.root, list)
        return list
    
	#Pre-order recursion helper, Time O(n) Space O(h) 
    def preHelper(self, node, list) :
        if node == None:
            return
        list.append(node.data)
        self.preHelper(node.left, list)
        self.preHelper(node.right, list)		
	
	
	#Post-order traversal, Recursion, Time O(n) Space O(n) 
    def postOrder(self) :
        list = []
        self.postHelper(self.root, list)
        return list
	
	#Post-order recursion helper, Time O(n), Space O(h)
    def postHelper(self, node, list) :
        if node == None: 
            return
        self.postHelper(node.left, list)
        self.postHelper(node.right, list)
        list.append(node.data);		

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

tree = BinarySearchTreeWithParent()
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
searchKey = 25
node = tree.searchDFS(searchKey)	    
print("\nDFS search:")
if node != None and node.parent == None:
    print(str(searchKey) + " is root")
elif node != None:
    print("find node: "+ str(node.data) + ", parent node: " + str(node.parent.data))
else:
    print(str(searchKey) + " is not found")

searchKey = 43
node = tree.searchBFS(searchKey)  
print("BFS search:")  
if node != None and node.parent == None:
    print(str(searchKey) + " is root")
elif node != None:
    print("find node: " + str(node.data) + ", parent node: " + str(node.parent.data))
else:
    print(str(searchKey) + " is not found")

#Delete 
deleteKey = 37
tree.root  = tree.delete(deleteKey)   
print("\nAfter delete " + str(deleteKey))
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 again
node = tree.searchDFS(searchKey)	    
if node != None and node.parent == None:
    print(str(searchKey) + " is root")
elif node != None:
    print("find node: " + str(node.data) + ", parent node: " + str(node.parent.data))
else:
    print(str(searchKey) + " is not found")