/**
 * An implemention of a linked binary tree
 * This implementation provides alternate implementations of many of the functions in
 * LinkedBinaryTree. Sometimes the alternate versions are more efficient or shorter.
 * The alternate versions do show different approaches to the same problem. 
 * 
 * @param <E>
 */
public class LinkedBinaryTreeAlt<E extends Comparable<E>> extends LinkedBinaryTree<E> {
	
	/**
	 * Create an empty LinnkedBinaryTree
	 */
	public LinkedBinaryTreeAlt() {
		root = null;
		size = 0;
	}


	/**
	 * Alternate implementation of size() that does not use the size instance
	 * variable
	 * 
	 * @return the number of nodes in the tree
	 */
	@Override
	public int size() {
		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 root == null;
	}

	@Override
	public E contains(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. 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);
			}
		}
	}

	@Override
	public void insert(E element) {
		root = insertAltUtil(root, element);
	}

	/**
	 * Version of insert that explicitly
	 * handles duplicates. Note that this method returns the root of the subtree
	 * investigated and always updates the subtree.   That way, if insert changes the root
	 * then the root will be updated smoothly. 
	 * This works much like the al version of remove, below.
	 * @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 E remove(E element) {
		E tmp = contains(element);
		if (tmp == null)
			return null;
		root = removeUtil(root, element);
		return tmp;
	}


	/**
	 * 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;
			}
		}
	}


	@Override
	public String breadthFirstListing() {
		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;
	}

}