/**
 * An implemention of a linked binary tree
 * 
 * @author gtowell Written: Feb 2020 
 * Updated: Mar 26, 2020 to fix right-left
 *         inversion throughout code 
 * Updated: Nov 2020 switchd some "alt" code
 *         to be the main code and updated documentation
 * 
 * 
 *         Methods with an @override annotation are documented in TreeInterface
 * 
 *         Methods named xxxAltxxx are alternative implementations. The
 *         alternatives have exactly the same effect, they just achieve it
 *         slightly differently.
 * @param <E>
 */
public class LinkedBinaryTree<E extends Comparable<E>> implements TreeInterface<E> {
	/**
	 * A class implementing the tree node Note that this inner class is declared as
	 * protected so it is available and visible to extending classes.
	 */
	protected class Node<F> {
		/** The data in the node */
		F payload;
		/** The right child */
		Node<F> right;
		/** The left child */
		Node<F> left;

		/**
		 * Node constructor. Just takes the data element. Sets the right and left to
		 * null
		 * 
		 * @param e the data element to be held in the node
		 */
		public Node(F e) {
			payload = e;
			right = null;
			left = null;
		}

		/**
		 * A print representation of the node. This just relies on the print rep of the
		 * payload
		 */
		public String toString() {
			return payload.toString();
		}
	}

	/** The number of elements in the tree */
	protected int size;
	/** The root of the tree */
	protected Node<E> root;

	/**
	 * Create an empty LinnkedBinaryTree
	 */
	public LinkedBinaryTree() {
		root = null;
		size = 0;
	}

	@Override
	public int size() {
		return size;
	}

	/**
	 * Alternate implementation of size() that does not use the size instance
	 * variable
	 * 
	 * @return the number of nodes in the tree
	 */
	public int sizeAlt() {
		return sizeAltUtil(root);
	}

	/**
	 * Private recursive helper method for size. Returns the size of the subtree
	 * rooted at treepart
	 * 
	 * @param treepart the root of a subtree
	 * @return the size of the subtree
	 */
	private int sizeAltUtil(Node<E> treepart) {
		if (treepart == null)
			return 0;
		return 1 + sizeAltUtil(treepart.left) + sizeAltUtil(treepart.right);
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	/**
	 * Alternate implementation of isEmpty that does not use the size instance
	 * variable Without size just check is the root is null
	 * 
	 * @return true iff the tree has no nodes.
	 */
	public boolean isEmptyAlt() {
		return root == null;
	}

	@Override
	public E contains(E element) {
		Node<E> tmp = containsUtil(root, element);
		if (tmp != null)
			return tmp.payload;
		return null;
	}

	/**
	 * Recursive helper function for determining if an element is in the tree. This
	 * version follows the algorithm and pseudocode in class. This version is clear
	 * because the base cases are at the top of the function.
	 * 
	 * @param treepart  the root of a subtree
	 * @param toBeFound the value to be looked for
	 * @return if found, the node containing the value, otherwise null.
	 */
	private Node<E> containsUtil(Node<E> treepart, E toBeFound) {
		if (treepart == null)
			return null;
		int cmp = treepart.payload.compareTo(toBeFound);
		if (cmp == 0)
			return treepart;
		if (cmp > 0) { // 3/26
			return containsUtil(treepart.left, toBeFound);
		} else {
			return containsUtil(treepart.right, toBeFound);
		}
	}

	/**
	 * Alternate version of contains. The major different in this version is that
	 * you check for null BEFORE recursion rather than after. In trees with a lot of
	 * leaves this can be quicker.
	 * 
	 * @param element the element to search the tree for
	 * @return the contained element or null
	 */
	public E containsAlt(E element) {
		if (root == null)
			return null;
		Node<E> tmp = containsAltUtil(root, element);
		if (tmp == null)
			return null;
		return tmp.payload;
	}

	/**
	 * Recursive helper function for determining if an element is in the tree.
	 * Checks for null before recursion so quicker. OTOH, the alt version has base
	 * cases for recursion throughtout the method.
	 * 
	 * @param treepart  the root of the current subtree to examine
	 * @param toBeFound the element being searched for
	 * @return true iff the element is in the tree.
	 */
	private Node<E> containsAltUtil(Node<E> treepart, E toBeFound) {
		int cmp = treepart.payload.compareTo(toBeFound);
		if (cmp == 0)
			return treepart;
		if (cmp > 0) { // 3/26
			if (treepart.left == null)
				return null;
			else
				return containsAltUtil(treepart.left, toBeFound);
		} else {
			if (treepart.right == null)
				return null;
			else {
				return containsAltUtil(treepart.right, toBeFound);
			}
		}
	}

	/**
	 * Alternate version of insert. IMHO, this version is far more comprehensible.
	 * It does, however, require more lines of code.
	 * 
	 * @param element the element to be added
	 */
	public void insertAlt(E element) {
		root = insertAltUtil(root, element);
	}

	/**
	 * Version of insert that closely follows the pseudocode and algorithm from
	 * lecture. This extends the algorithm from lecture in that it explicitly
	 * handles duplicates. Note that this method returns the root of the subtree
	 * investigated and always updates the subtree.
	 * 
	 * @param treepart the root of the current subtree
	 * @param element  the element to insert
	 * @return
	 */
	private Node<E> insertAltUtil(Node<E> treepart, E element) {
		if (treepart == null) {
			size++;
			return new Node<E>(element);
		}
		int cmp = treepart.payload.compareTo(element);
		if (cmp == 0)
			return treepart;
		if (cmp > 0) {
			treepart.left = insertAltUtil(treepart.left, element);
			return treepart;
		} else {
			treepart.right = insertAltUtil(treepart.right, element);
			return treepart;
		}
	}

	@Override
	public void insert(E element) {
		if (root == null) {
			root = new Node<E>(element);
			size = 1;
		} else
			insertUtil(root, element);
	}

	/**
	 * Alterate recursive helper function for insertion of an element into a tree.
	 * Again, watch out for base cases.
	 * 
	 * @param treepart  the root of the current subtree
	 * @param toBeAdded the element to be added to the tree
	 */
	private void insertUtil(Node<E> treepart, E toBeAdded) {
		int cmp = treepart.payload.compareTo(toBeAdded);
		if (cmp == 0)
			return; // the item is in the tree
		if (cmp > 0) { // Mar 26 fixed wrong direction on comparison
			//System.out.println(toBeAdded + " is less than " + treepart.payload + " so left in tree");
			if (treepart.left == null) {
				size++;
				treepart.left = new Node<E>(toBeAdded);
			} else {
				insertUtil(treepart.left, toBeAdded);
			}
		} else {// cmp>0
			//System.out.println(toBeAdded + " is greater than " + treepart.payload + " so right in tree");

			if (treepart.right == null) {
				size++;
				treepart.right = new Node<E>(toBeAdded);
			} else {
				insertUtil(treepart.right, toBeAdded);
			}
		}
	}

	@Override
	public E remove(E element) {
		E tmp = contains(element);
		if (tmp == null)
			return null;
		root = removeUtil(root, element);
		return tmp;
	}

	/**
	 * Find the value stored in the leftmost node of the tree
	 * 
	 * @param sRoot the subtree root
	 * @return the data leement in the left most node of the subtree
	 */
	private E minKey(Node<E> sRoot) {
		if (sRoot.left == null)
			return sRoot.payload;
		else
			return minKey(sRoot.left);
	}

	/**
	 * Find the maximum value in the tree rooted at the given node
	 * 
	 * @param treepart the subtree root
	 * @return the data element in the right most node of the subtree
	 */
	@SuppressWarnings("unused")
	private E maxKey(Node<E> treepart) {
		if (treepart.right == null)
			return treepart.payload;
		else
			return maxKey(treepart.right);
	}

	/**
	 * Find the maximum value in the tree rooted at the given node, and do it
	 * without recursion.
	 * 
	 * @param treepart the subtree root
	 * @return the data element in the right most node of the subtree
	 */
	@SuppressWarnings("unused")
	private E maxKeyNR(Node<E> treepart) {
		Node<E> rightChild = treepart.right;
		while (rightChild != null) {
			treepart = rightChild;
			rightChild = treepart.right;
		}
		return treepart.payload;
	}

	/**
	 * Recursive helper function for removing a node with the given element
	 * 
	 * @param sRoot   the root of the subtree being examined.
	 * @param element the element to be removed.
	 * @return the root of the subtree after element deletion
	 */
	private Node<E> removeUtil(Node<E> sRoot, E element) {
		if (sRoot == null)
			return null;
		int cmpr = sRoot.payload.compareTo(element);
		if (cmpr > 0) {
			sRoot.left = removeUtil(sRoot.left, element);
			return sRoot;
		} else if (cmpr < 0) {
			sRoot.right = removeUtil(sRoot.right, element);
			return sRoot;
		} else { // == 0
			if (sRoot.right == null) { // this will also get a node with no children.
				size--;
				return sRoot.left;
			} else if (sRoot.left == null) {
				size--;
				return sRoot.right;
			} else {
				// two children
				// no size--because this node is not being removed!
				E pred = minKey(sRoot.right);
				sRoot.payload = pred;
				sRoot.right = removeUtil(sRoot.right, pred);
				return sRoot;
			}
		}
	}

	/**
	 * An alternate version of remove. Considerably longer, but more easily
	 * understood.
	 * 
	 * @param element the element to be removed
	 * @return true iff the element is in the tree
	 */
	public boolean removeAlt(E element) {
		if (root == null)
			return false;
		return removeAltUtil(root, null, element);
	}

	/**
	 * Internal, recursive implementation of remove
	 * 
	 * @param treepart    the root of the current subtree
	 * @param parent      the parent of the root of the current subtree
	 * @param toBeRemoved the element to be removed.
	 * @return true iff toBeRemoved is in the tree.
	 */
	private boolean removeAltUtil(Node<E> treepart, Node<E> parent, E toBeRemoved) {
		if (treepart == null)
			return false;
		int cmp = treepart.payload.compareTo(toBeRemoved);
		if (cmp > 0) {
			System.out.println(toBeRemoved + " is less than " + treepart.payload + " so left in tree");
			return removeAltUtil(treepart.left, treepart, toBeRemoved);
		} else if (cmp > 0) {
			System.out.println(toBeRemoved + " is greater than " + treepart.payload + " so right in tree");
			return removeAltUtil(treepart.right, treepart, toBeRemoved);
		} else { // cmp==0
			// this is the thing I want to get rid of!!!!
			if (treepart.left == null && treepart.right == null) {
				// Case 2: no children
				if (parent == null) {
					root = null;
				} else {
					if (parent.right == treepart)
						parent.right = null;
					else
						parent.left = null;
				}
				size--;
				return true;
			}
			if (treepart.left == null) { // the right branch is NOT null
				// Case 3: Only a right child
				if (parent == null) {
					root = treepart.right;
				} else {
					if (parent.right == treepart)
						parent.right = treepart.right;
					else
						parent.left = treepart.right;
				}
				size--;
				return true;
			}
			if (treepart.right == null) {
				// Case 3: only a left child
				if (parent == null) {
					root = treepart.left;
				} else {
					if (parent.right == treepart)
						parent.right = treepart.left;
					else
						parent.left = treepart.left;
				}
				size--;
				return true;
			}
			// case 4: Two children
			E pred = minKey(treepart.right);
			removeAltUtil(treepart.right, treepart, pred);
			treepart.payload = pred;
			return true;
		}

	}

	@Override
	public int height() {
		return maxDepthUtil(root) - 1;
	}

	/**
	 * An internal recursive helper function to calculate the height of the tree
	 * with the given root.
	 * 
	 * @param node the root of the subtree for which the height is desired
	 * @return
	 */
	private int maxDepthUtil(Node<E> node) {
		if (node == null)
			return 0;
		int rd = maxDepthUtil(node.right) + 1;
		int ld = maxDepthUtil(node.left) + 1;
		if (rd > ld)
			return rd;
		else
			return ld;
	}

	/**
	 * Print the tree in postorder The tree data will be printed on a single line
	 * with each node appearing as [payload,depth]
	 */
	public void printPostOrder() {
		iPrintPostOrder(root, 0);
		System.out.println();
	}

	/**
	 * Recursive helper function for postorder printing.
	 * 
	 * @param treePart the root of the current subtree
	 * @param depth    the depth of the root of the current subtree.
	 */
	private void iPrintPostOrder(Node<E> treePart, int depth) {
		if (treePart == null)
			return;
		iPrintPostOrder(treePart.left, depth + 1);
		iPrintPostOrder(treePart.right, depth + 1);
		System.out.print("[" + treePart.payload + "," + depth + "]");
	}

	@Override
	public String printNaturalOrder() {
		return "";
	}

	public String breadthFirstListing() {
		StringBuffer collect = new StringBuffer();
		for (int targetLevel=0; targetLevel<=height(); targetLevel++) {
			collect.append(targetLevel + " [");
			bfUtil(root, targetLevel, 0, collect);
			collect.append("]\n");
		}
		return collect.toString();
	}

	private void bfUtil(Node<E> node, int targetLevel, int currentLevel, StringBuffer buf) {
		if (node == null)
			return;
		if (targetLevel == currentLevel) {
			buf.append(" " + node.payload.toString());
			return;
		}
		bfUtil(node.left, targetLevel, currentLevel + 1, buf);
		bfUtil(node.right, targetLevel, currentLevel + 1, buf);
	}

	public String breadthFirstListingAlt() {
		StringBuffer collect = new StringBuffer();
		for (int targetLevel=0; targetLevel<=1000000; targetLevel++) {
			collect.append(targetLevel + " [");
			if (!bfUtilAlt(root, targetLevel, 0, collect)) break;
			collect.append("]\n");
		}
		return collect.toString();
	}

	private boolean bfUtilAlt(Node<E> node, int targetLevel, int currentLevel, StringBuffer buf) {
		if (node == null)
			return false;
		if (targetLevel == currentLevel) {
			buf.append(" " + node.payload.toString());
			return true;
		}
		boolean l = bfUtilAlt(node.left, targetLevel, currentLevel + 1, buf);
		boolean r = bfUtilAlt(node.right, targetLevel, currentLevel + 1, buf);
		return l || r;
	}

}