/**
* This entire class is used to build a Binary Tree data structure.
* There is the Node Class and the Tree Class, both explained below.
*
* @author Unknown
*
*/


/**
* This class implements the nodes that will go on the Binary Tree.
* They consist of the data in them, the node to the left, the node
* to the right, and the parent from which they came from.
*
* @author Unknown
*
*/
class Node{
	/** Data for the node */
	public int data;
	/** The Node to the left of this one */
	public Node left;
	/** The Node to the right of this one */
	public Node right;
	/** The parent of this node */
	public Node parent;

	/**
	* Constructor of Node
	*
	* @param value Value to put in the node
	*/
	public Node(int value){
		data = value;
		left = null;
		right = null;
		parent = null;
	}
}


/**
* A binary tree is a data structure in which an element
* has two successors(children). The left child is usually
* smaller than the parent, and the right child is usually
* bigger.
*
* @author Unknown
*
*/
class Tree{
	/** The root of the Binary Tree */
	private Node root;

	/**
	* Constructor
	*/
	public Tree(){
		root = null;
	}

	/**
	* Method to find a Node with a certain value
	*
	* @param key Value being looked for
	* @return The node if it finds it, otherwise returns the parent
	*/
	public Node find(int key) {
		Node current = root;
		while (current != null) {
			if(key < current.data) {
				if(current.left == null)
					return current;	//The key isn't exist, returns the parent
				current = current.left;
			} else if(key > current.data) {
				if(current.right == null)
					return current;	
				current = current.right;
			} else {	// If you find the value return it
				return current;
			}
		}
		return null;
	}

	/**
	* Inserts certain value into the Binary Tree
	*
	* @param value Value to be inserted
	*/
	public void put(int value){
		Node newNode = new Node(value);
		if(root == null)
		root = newNode;
		else{
			//This will return the soon to be parent of the value you're inserting
			Node parent = find(value);

			//This if/else assigns the new node to be either the left or right child of the parent
			if(value < parent.data){
				parent.left = newNode;
				parent.left.parent = parent;
				return;
			}
			else{
				parent.right = newNode;
				parent.right.parent = parent;
				return;
			}
		}
	}

	/**
	* Deletes a given value from the Binary Tree
	*
	* @param value Value to be deleted
	* @return If the value was deleted
	*/
	public boolean remove(int value){
		//temp is the node to be deleted
		Node temp = find(value);

		//If the value doesn't exist
		if(temp.data != value)
		return false;

		//No children
		if(temp.right == null && temp.left == null){
			if(temp == root)
			root = null;

			//This if/else assigns the new node to be either the left or right child of the parent
			else if(temp.parent.data < temp.data)
			temp.parent.right = null;
			else
			temp.parent.left = null;
			return true;
		}

		//Two children
		else if(temp.left != null && temp.right != null){
			Node successor = findSuccessor(temp);

			//The left tree of temp is made the left tree of the successor
			successor.left = temp.left;
			successor.left.parent = successor;

			//If the successor has a right child, the child's grandparent is it's new parent
			if(successor.right != null && successor.parent != temp){
				successor.right.parent = successor.parent;
				successor.parent.left = successor.right;
				successor.right = temp.right;
				successor.right.parent = successor;
			}
			if(temp == root){
				successor.parent = null;
				root = successor;
				return true;
			}

			//If you're not deleting the root
			else{
				successor.parent = temp.parent;

				//This if/else assigns the new node to be either the left or right child of the parent
				if(temp.parent.data < temp.data)
				temp.parent.right = successor;
				else
				temp.parent.left = successor;
				return true;
			}
		}
		//One child
		else{
			//If it has a right child
			if(temp.right != null){
				if(temp == root){
					root = temp.right; return true;}

					temp.right.parent = temp.parent;

					//Assigns temp to left or right child
					if(temp.data < temp.parent.data)
					temp.parent.left = temp.right;
					else
					temp.parent.right = temp.right;
					return true;
				}
				//If it has a left child
				else{
					if(temp == root){
						root = temp.left; return true;}

						temp.left.parent = temp.parent;

						//Assigns temp to left or right side
						if(temp.data < temp.parent.data)
						temp.parent.left = temp.left;
						else
						temp.parent.right = temp.left;
						return true;
					}
				}
			}

			/**
			* This method finds the Successor to the Node given.
			* Move right once and go left down the tree as far as you can
			*
			* @param n Node that you want to find the Successor of
			* @return The Successor of the node
			*/
			public Node findSuccessor(Node n){
				if(n.right == null)
				return n;
				Node current = n.right;
				Node parent = n.right;
				while(current != null){
					parent = current;
					current = current.left;
				}
				return parent;
			}

			/**
			* Returns the root of the Binary Tree
			*
			* @return the root of the Binary Tree
			*/
			public Node getRoot(){
				return root;
			}

			/**
			* Prints leftChild - root - rightChild
			*
			* @param localRoot The local root of the binary tree
			*/
			public void inOrder(Node localRoot){
				if(localRoot != null){
					inOrder(localRoot.left);
					System.out.print(localRoot.data + " ");
					inOrder(localRoot.right);
				}
			}

			/**
			* Prints root - leftChild - rightChild
			*
			* @param localRoot The local root of the binary tree
			*/
			public void preOrder(Node localRoot){
				if(localRoot != null){
					System.out.print(localRoot.data + " ");
					preOrder(localRoot.left);
					preOrder(localRoot.right);
				}
			}

			/**
			* Prints rightChild - leftChild - root
			*
			* @param localRoot The local root of the binary tree
			*/
			public void postOrder(Node localRoot){
				if(localRoot != null){
					postOrder(localRoot.left);
					postOrder(localRoot.right);
					System.out.print(localRoot.data + " ");
				}
			}
		}