package final_repitition;



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(int data,Node left,Node right){
			this.data = data;
			this.left = left;
			this.right = right;
		}
		public String toString(){
			return ""+this.data;
		}
	}

	Node root;

	public BST(){
		root = null;
	}

	public void add(int data){
		if(root==null){
			root = new Node(data);
		}else{
			addRec(root,data);
		}
	}

	private Node addRec(Node cur,int data){
		if(cur == null){
			cur = new Node(data);
		}
		if(data>cur.data){
			cur.left = addRec(cur.left,data);
		}
		else if(data<cur.data){
			cur.right = addRec(cur.right,data);
		}

		return cur;
	}

	public String toString(){
		return recToString(root,0);
	}

	public String recToString(Node c,int depth){
		if(c==null){
			return "null";
		}

		String ret = "";
		if(c==root){
			ret+="Root:";
		}
		ret += "value:"+c.data;


		if(c.left==null && c.right==null){
			return ret;
		}
		ret+="\n";
		for(int i=0;i<depth+1;i++){ret+="   ";}
		ret += "Left:" + recToString(c.left,depth+1);
		ret+="\n";
		for(int i=0;i<depth+1;i++){ret+="   ";}
		ret += "Right:" + recToString(c.right,depth+1);

		return ret;
	}

	public boolean find(int data){
		return findRec(root,data);
	}

	private boolean findRec(Node c,int data){
		if(c==null){
			return false;
		}
		if(c.data==data){
			return true;
		}
		else if(data>c.data){
			return findRec(c.left,data);
		}
		else{
			return findRec(c.right,data);
		}

	}

	public String inOrder(){
		return inOrderRec(root);
	}

	private String inOrderRec(Node c){
		String result = "";
		if(c==null){
			return "";
		}
		result+=inOrderRec(c.left)+""+c+""+inOrderRec(c.right);
		return result;
	}

	public String postOrder(){
		return postOrderRec(root);
	}

	private String postOrderRec(Node c){
		String result = "";
		if(c==null){
			return "";
		}
		result+=postOrderRec(c.left)+""+postOrderRec(c.right)+""+c;
		return result;
	}

	public String preOrder(){
		return preOrderRec(root);
	}

	private String preOrderRec(Node c){
		String result = "";
		if(c==null){
			return "";
		}
		result+=c+""+preOrderRec(c.left)+""+preOrderRec(c.right)+"";
		return result;
	}

	public boolean delete(int data){
		Node parent = root;
		Node current = root;
		boolean left = false;
		while(current.data!=data){
			parent = current;
			if(current.data>data){
				left = false;
				current = current.right;
			}
			else{
				left = true;
				current = current.left;
			}
			if(current==null){
				return false;
			}
		}

		if(current.left == null && current.right == null){
			System.out.println("Both null");
			if(current==root){
				root=null;
			}
			if(left){
				parent.left = null;
			}
			else{
				parent.right = null;
			}
		}

		else if(current.right == null){
			System.out.println("Right null");
			if(current==root){
				root = current.left;
			}else if(left){
				parent.left = current.left;
			}else{
				parent.right = current.left;
			}
		}
		else if(current.left == null){
			System.out.println("left null");
			if(current == root){
				root = current.right;
			}
			else if(left){
				parent.left = current.right;
			}
			else{
				parent.right= current.right;
			}
		}
		else if(current.left!=null && current.right!=null){
			System.out.println("Both not null");
			Node successor = getSuccessor(current);
			if(current==root){
				root = successor;
			}
			else if(left){
				parent.left = successor;
			}
			else{
				parent.right = successor;
			}
		}

		return true;


	}

	private Node getSuccessor(Node deleteNode){
		Node successor = null;
		Node successorParent = null;
		Node current = deleteNode.right;

		while(current!=null){
			successorParent = successor;
			successor = current;
			current = current.left;
		}

		if(successor!=deleteNode.right){
			successorParent.left = successor.right;
			successor.right = deleteNode.right;
		}


		return successor;
	}


	public static void main(String [] args){
		BST bst = new BST();
		bst.add(3);
		bst.add(5);
		bst.add(2);
		bst.add(1);
		bst.add(4);
		bst.add(6);


		System.out.println("Find(1):"+bst.find(1));
		System.out.println("Find(10):"+bst.find(10));
		System.out.println("Find(4):"+bst.find(4));

		System.out.println("InOrder:" + bst.inOrder());
		System.out.println("PostOrder:"+ bst.postOrder());
		System.out.println("PreOrder:"+ bst.preOrder());


		System.out.println("Before delete:");
		System.out.println(bst);
		System.out.println("After delete:");
		System.out.println(bst.delete(5));
		System.out.println(bst);

	}
}