import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BST {

	class Node {
		int data;
		Node left;
		Node right;

		public Node(int data) {

			this.data = data;
			this.left = null;
			this.right = null;
		}
	}

	public Node insertNode(Node root, int data) {

		if (root == null) {
			Node newNode = new Node(data);
			root = newNode;
		} else if (root.data >= data) {
			root.left = insertNode(root.left, data);
		} else {
			root.right = insertNode(root.right, data);
		}
		return root;
	}

	public Node insertNodeUsingLoop(Node root, int data) {

		if (root == null) {
			Node newNode = new Node(data);
			root = newNode;
		} else if (root.data >data) {

			if (root.left == null) {
				Node newNode = new Node(data);
				root.left = newNode;
			} else {

				Node temp = root.left;
				Node prev=null;
				char side='L';
				while (temp != null) {
					prev=temp;
					if (temp.data > data) {
						temp = temp.left;
						side='L';
					} else {
						temp = temp.right;
						side='R';
					}
				}
				if(prev.data!=data){
				Node newNode = new Node(data);
				if(side=='L')
					prev.left=newNode;
				else
					prev.right=newNode;
				}
			}

		} else {
			if (root.right == null) {
				Node newNode = new Node(data);
				root.right = newNode;
			} else {
				Node temp = root.right;
				Node prev=null;
				char side='R';
				
				while (temp != null) {
					prev=temp;
					if (temp.data > data) {
						temp = temp.left;
						side='L';
					} else {
						temp = temp.right;
						side='R';
					}
				}
				if(prev.data!=data){
				Node newNode = new Node(data);
//				newNode = (side=='L' )? prev.left :prev.right;
				if(side=='L')
					prev.left=newNode;
				else
					prev.right=newNode;
				}
			}
		}

		return root;
	}

	public void printTree(Node root) {

		if (root == null) {
			return;
		} else {

			printTree(root.left);
			System.out.print(root.data+" ");
			printTree(root.right);
			// System.out.println(root.data);

		}

	}

	public boolean search(Node root, int data) {

		if (root == null) {
			System.err.println("Not found");
			return false;
		}
		if (root.data == data) {
			System.out.println("Found");
			return true;
		}
		if (root.data > data)
			search(root.left, data);
		else
			search(root.right, data);

		return false;
	}
	
	public static Node deleteNodeWithOneChild(Node delNode){
		
		if(delNode.right!=null){
			
			delNode=delNode.right;
		}else{
			delNode=delNode.left;
		}
		
		
		return delNode;
	}
	/**
	 * First we find the minimum in right subtree and delete the minimum node 
	 * and then replace the node to be deleted with the min value
	 * @param root
	 * @return
	 */
	private Node deleteNodeWithTwoChild(Node root) {
		
		int d = findMin(root.right);
		this.delete(root, d);
		root.data=d;
		return root;
	}	
	/**
	 * Three cases:
	 * 1) Node to be deleted is leaf: Simply remove from the tree.
	 * 2) Node to be deleted has only one child: Copy the child to the node and delete the child
	 *3) Node to be deleted has two children:
	 * @param root
	 * @param data
	 * @return
	 */
	public Node delete(Node root, int data){
		if(root==null) return null;
		if(root.data==data){
			
			if(root.left !=null || root.right != null  ){
				if(root.left !=null && root.right!=null)
					root=deleteNodeWithTwoChild(root);
				else
					root=deleteNodeWithOneChild(root);
			}
			else
				root=null;
			
		}
		else if(root.data>data){
			
			root.left=delete(root.left, data);
		}else{
			root.right=delete(root.right, data);
		}
		
		return root;
	}
	
	

	
	public int findMin(Node root){
	
		if(root==null) 
			return -1;
		else if(root.left==null ) 
			return root.data;
			
		return findMin(root.left);	
			
		
		
	}
	
	Node maxNode=null;
	public Node findMax(Node root){
		
		Node temp=root;
		
		if(root==null) return null;
		else{
			temp.right=findMax(root.right);
			if(temp.left==null){
				maxNode=temp;
			}
		}
		
		return maxNode;
		
	}
	
	
	public int getMax(Node root){
		
		if(root==null) return -1;
		if(root.right==null){
			return root.data;
		}
		
		return getMax(root.right);
	}
	
	/**
	 * Height will be 1 + max(heightof left subtree , height of right subtree)
	 * 
	 * @param args
	 */
	public int findHeight(Node root){
		
		if(root==null){
			return -1;
		}
		System.out.println("before::"+root.data);
		int leftHeight = findHeight(root.left);
		System.out.println("LeftHeight ::"+leftHeight);
		System.out.println("After ::"+root.data);
		int rightHeight=findHeight(root.right);
		System.out.println("RightHeight:: "+rightHeight);
		return 1+ Math.max(leftHeight, rightHeight);
	}
	
	 /**
	  * 
	  * Level order traversal means traversing  the tree level by level
	  * This is also called breadth first traversal
	  * we will use the queue to store the discovered nodes 
	  * @param args
	  */
	public void levelOrderTraversal(Node root){
		
		Queue<Node> q=new LinkedList<>();
		q.add(root);
		System.out.print("\n[ ");
		while(!q.isEmpty()){
			
			System.out.print(q.peek().data+",");
			if(q.peek().left!=null) q.add(q.peek().left);
			if(q.peek().right!=null) q.add(q.peek().right);
			q.remove();
		}
		System.out.println("]");
	}
	
	public void preOrderTraversal(Node root){
		
		if(root==null)
			return;
		System.out.print(root.data+",");
		preOrderTraversal(root.left);
		preOrderTraversal(root.right);
		
	}
	
	public void postOrderTraversal(Node root){
		if(root==null)
			return;
		postOrderTraversal(root.left);
		postOrderTraversal(root.right);
		System.out.print(root.data+",");
	}
	
	public void verticalUtil(Node root,int index,HashMap<Integer, Integer> hm){
		
		if(root==null)
		{
			return;
		}
		else{
			
			verticalUtil(root.left, index-1, hm);
			if(hm.containsKey(index)){
				System.out.println("repeated index"+index);
				hm.put(index, hm.get(index)+root.data);
			}else
				hm.put(index, root.data);
			
			verticalUtil(root.right, index+1, hm);
		}
	}
	
	public void verticalSum(Node root){
		HashMap<Integer, Integer> hm = new HashMap<>();
		verticalUtil(root, 0, hm);
		System.out.println();
		System.out.println(hm);
//		return 1;
	}
   public static void main(String[] args) {
		Node root = null;
		BST tree = new BST();
		root = tree.insertNode(root, 16);
		root = tree.insertNode(root, 17);
		root = tree.insertNode(root, 8);
		root = tree.insertNode(root, 10);
		root = tree.insertNode(root, 9);
		root = tree.insertNode(root, 11);
		root = tree.insertNode(root, 2);
		
		tree.printTree(root);
		tree.search(root, 18);
//		tree.search(root, 180);
		
//		root=tree.delete(root, 8);
		tree.printTree(root);
		
		
		System.out.println("Max::"+tree.getMax(root));
		tree.printTree(root);
		tree.levelOrderTraversal(root);
		tree.preOrderTraversal(root);
		System.out.println("\nPostorder");
		tree.postOrderTraversal(root);
//		System.out.println("height finding");
//		System.out.println("Height is "+tree.findHeight(root));
		
		
//		tree.delete(root, 8);
		System.out.println("\nPrinting tree after deletion");
		tree.printTree(root);
		System.out.println("\nPrinting tree after deletion 9");
		tree.delete(root, 9);
		tree.printTree(root);
		tree.verticalSum(root);
	}
}