import java.util.*;

public class BinarySearchTreeWithParent<T extends Comparable<T>> {
	
	//TreeNode with a parent reference
	static class TreeNode<T> {		
		T data;
		TreeNode<T> left = null;        
		TreeNode<T> right = null;
		TreeNode<T> parent = null;	

	    //Override, Time O(1), Space O(1)
		 @Override
	    public String toString() {
	    	return String.valueOf(data);
	    }
	}  
	
	TreeNode<T> root = null;
	
	//Insert with parent pointer, Iteration, Time O(h) Space O(1), h is height of tree
	public void insert(T value) {
		TreeNode<T> newNode = new TreeNode<>();    
		newNode.data = value; 
		if(root == null) {            
			root = newNode;
			return;
		}		
		TreeNode<T> curr = root;       
		TreeNode<T> parent;
		while(true) {
			parent = curr;
			if(value.compareTo(curr.data) < 0) {
				curr = curr.left;
				if(curr == null) {                
					parent.left = newNode;
					newNode.parent = parent;
					return;
				}
			} else {
				curr = curr.right;
				if(curr == null) {                 
					parent.right = newNode;
					newNode.parent =parent;
					return;
				}
			}  
		}  		
	} 
	
	//Delete with parent pointer, Iteration, Time O(h) Space O(1)
    public TreeNode<T> delete(T key) {
        if (root == null )
        	return null;
        if (root.data == key){ //delete root
        	root = deleteNode(root); //reset the root
        	root.parent = null;
        	return root;
        }
        TreeNode<T> curr = root;     
        while (true) { 
            if (key.compareTo(curr.data) > 0) {
                if (curr.right == null )
                	break;
                else if (curr.right.data == key) {
                	TreeNode<T> oldParent = curr.right.parent;
                    curr.right = deleteNode(curr.right);
                    if (curr.right != null)
                    	curr.right.parent = oldParent;
                    break;
                }
                curr = curr.right;
            } else {
                if (curr.left == null)
                	break;
                else if (curr.left.data == key) {
                	TreeNode<T> oldParent = curr.right.parent;
                    curr.left = deleteNode(curr.left);
                    if (curr.left != null)
                    	curr.left.parent = oldParent;
                    break;
                }
                curr = curr.left;
            }
        }
        return root;
    }
    
    //Delete node, Time O(h), Space O(1)
    private TreeNode<T> deleteNode(TreeNode<T> node) {
        if (node == null) 
        	return null;
        if (node.right == null) 
        	return node.left;
        TreeNode<T> curr = node.right;
        while (curr.left != null) //find the left-most node
        	curr = curr.left; 
        curr.left = node.left; // put the original left under left most, 
        if (node.left!=null)
        	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)
	TreeNode<T> searchDFS(T key) {
		return dfsHelper(root, key);		
	}
	
	//Search recursion helper, Time O(h) Space O(h)
	private TreeNode<T> dfsHelper(TreeNode<T> node, T key) {
		if(node == null) 
            return null;       
        if(node.data == key) 
            return node;
        return key.compareTo(node.data) > 0 ? dfsHelper(node.right, key) : dfsHelper(node.left, key);
    }	
		
    //Iteration, Time O(h) Space O(1)
	public TreeNode<T> searchBFS(T key) {                           
		TreeNode<T> curr = root;               
		while (curr != null) {
			if (curr.data == key)
				return curr;
			else if (key.compareTo(curr.data) < 0)
				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 tree
	public List<T> inOrder() {
		List<T> list = new ArrayList<>();
        inHelper(root, list);
        return list;
    }
	
	//In-order recursion helper, Time O(n), Space O(h) 
	private void inHelper(TreeNode<T> node, List<T> list) {
		if (node == null) 
			return;
		inHelper(node.left, list);
		list.add(node.data);
		inHelper(node.right, list);	
	}
	
	//Pre-order traversal, recursion, Time O(n), Space O(n) 
	public List<T> preOrder() {
		List<T> list = new ArrayList<>();
        preHelper(root, list);
        return list;
    }
	
	//Pre-order recursion helper, Time O(n) Space O(h) 
	private void preHelper(TreeNode<T> node, List<T> list) {
		if (node == null)
			return;
		list.add(node.data);
		preHelper(node.left, list);
		preHelper(node.right, list);		
	}
	
	//Post-order traversal, Recursion, Time O(n) Space O(n) 
	public List<T> postOrder() {
		List<T> list = new ArrayList<>();
        postHelper(root, list);
        return list;
    }	
	
	//Post-order recursion helper, Time O(n), Space O(h)
	private void postHelper(TreeNode<T> node, List<T> list) {
		if (node == null) 
			return;
		postHelper(node.left, list);
		postHelper(node.right, list);
		list.add(node.data);		
	}
	
	//Level order traversal, Time O(n), Space O(n)
	public List<T> levelOrder() {
		if (root == null)
			return null;	
		List<T> list = new ArrayList<>();
		Queue<TreeNode<T>> q = new LinkedList<>();
		q.add(root);		
		while (!q.isEmpty()) {
			TreeNode<T> curr = q.poll();
			list.add(curr.data);
			if(curr != null) {
				if (curr.left != null) 
					q.add(curr.left);
				if (curr.right != null) 	
					q.add(curr.right);	
			} 
		}
		return list;
	}
	
	public static void main(String[] args) {		
		//Build tree and traversal
		BinarySearchTreeWithParent<Integer> tree = new BinarySearchTreeWithParent<>();
	    tree.insert(50);
	    tree.insert(12);
	    tree.insert(25);
	    tree.insert(75);
	    tree.insert(37);
	    tree.insert(22);
	    tree.insert(43);
	    System.out.println("The root: " + tree.root.data); 

		System.out.println("Preorder: " + tree.preOrder());
		System.out.println("Inorder: " + tree.inOrder());
		System.out.println("Postorder: " + tree.postOrder()); 
		System.out.println("Level order: " + tree.levelOrder());
	    
	    //search
	    int searchKey = 25;
	    TreeNode<Integer> node = tree.searchDFS(searchKey);	    
	    System.out.print("\nDFS search: ");
	    if (node != null && node.parent == null)
	    	System.out.println("it is root");
	    else if(node != null)
	    	System.out.println("find node: " + node.data + ", parent node: " + node.parent.data);
	    else
	    	System.out.println("node is not found");
	    
	    searchKey = 43;
	    node = tree.searchBFS(searchKey);	    
	    System.out.print("BFS search: ");
	    if (node != null && node.parent == null)
	    	System.out.println(node.data + " is root");
	    else if(node != null)
	    	System.out.println("find node: " + node.data + ", parent node: " + node.parent.data);
	    else
	    	System.out.println(searchKey + " is not found");
	    
	    //Delete 
	    int deleteKey = 25;	 //delete    
	    tree.root  = tree.delete(deleteKey);    
	    System.out.println("\nAfter delete " + deleteKey);
	    System.out.println("The root: " + tree.root.data); 
		System.out.println("Preorder: " + tree.preOrder());
		System.out.println("Inorder: " + tree.inOrder());
		System.out.println("Postorder: " + tree.postOrder()); 
		System.out.println("level order: " + tree.levelOrder());
		
		//search again
	    node = tree.searchDFS(searchKey);	    
	    if (node != null && node.parent == null)
	    	System.out.println(node.data + " is root");
	    else if(node != null)
	    	System.out.println("find node: "+node.data + ", parent node: " + node.parent.data);
	    else
	    	System.out.println(searchKey + " is not found");		
	}
}