import java.util.*;

public class BinarySearchTree<T extends Comparable<T>> {	
	
	static class TreeNode<T> {		
		T data;
		TreeNode<T> left = null;        
		TreeNode<T> right = null;
	
	    //Override, Time O(1), Space O(1)
		 @Override
	    public String toString() {
	    	return String.valueOf(data);
	    }
	}  
	
	TreeNode<T> root = null;
	
	//Insert a node based on value, 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> prev;
		while (true) {
			prev = curr;
			if (value.compareTo(curr.data) < 0) {
				curr = curr.left;
				if (curr == null) {                 
					prev.left = newNode;
					return;
				}
			} else {
				curr = curr.right;
				if (curr == null) {                 
					prev.right = newNode;
					return;
				}
			}  
		}	
	} 

	//Delete node by key, Iteration, Time O(h), Space O(1)
    public TreeNode<T> delete(T key) {
       if (root == null)
        	return null;
       if (root.data == key) { 
        	root = getSuccessor(root);       	
        	return root;
        }        
        TreeNode<T> curr = root;     
        while (true) { 
            if (key.compareTo(curr.data) > 0) {
                if (curr.right == null || curr.right.data == key) {
                    curr.right = getSuccessor(curr.right);
                    break;
                }
                curr = curr.right;
            } else {
                if (curr.left == null || curr.left.data == key) {
                    curr.left = getSuccessor(curr.left);
                    break;
                }
                curr = curr.left;
            }
        }
        return root;
    }
    
    //Delete node, return next successor, Time O(h), Space O(1)
    private TreeNode<T> getSuccessor(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;
        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)
	public 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;                    
	} 
	
	//Inorder traversal, Time O(n), Space O(n), n is number of nodes in trees
	public List<T> inorder() {
		List<T> list = new ArrayList<>();
        inorderRec(root, list);
        return list;
    }
	
	//Inorder recursion helper, Time O(n), Space O(h)
	public void inorderRec(TreeNode<T> node, List<T> list) {
		if (node == null) 
			return;
		inorderRec(node.left, list);
		list.add(node.data);
		inorderRec(node.right, list);		
	}
	
	//Preorder traversal, Time O(n), Space O(n) 
	public List<T> preorder() {
		List<T> list = new ArrayList<>();
        preorderRec(root, list);
        return list;
    }

	//Preorder recursion helper, Time O(n), Space O(h) 
	private void preorderRec(TreeNode<T> node, List<T> list) {
		if (node == null)
			return;
		list.add(node.data);
		preorderRec(node.left, list);
		preorderRec(node.right, list);		
	}
	
	//Postorder traversal, Time O(n), Space O(n) 
	public List<T> postorder() {
		List<T> list = new ArrayList<>();
        postorderRec(root, list);
        return list;
    }	
	
	//Postorder recursion helper, Time O(n), Space O(h) 
	private void postorderRec(TreeNode<T> node, List<T> list) {
		if (node == null) 
			return;
		postorderRec(node.left, list);
		postorderRec(node.right, list);
		list.add(node.data);		
	}
	
	//Level order traversal, Iteration, 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 
		BinarySearchTree<Integer> tree = new BinarySearchTree<>();
	    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 key = 37;
	    TreeNode<Integer> node = tree.searchDFS(key);
	    System.out.println("\nDFS search " + key + ", node data: " + node);
	    
	    key = 25;
	    node = tree.searchBFS(key);
	    System.out.println("BFS Search " + key + ", node data: " + node);
	    
	    //Delete 
	    key = 25;	  
	    tree.root  = tree.delete(key);    
	    System.out.println("\nAfter delete " + key);
	    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());	
			
	    node = tree.searchDFS(key);
	    System.out.println("DFS search " + key + ", node data: " + node);
	}
}