/**
 * 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.
 * Updated: Nov 2021 -- moved "alt" code to separate class
 * @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 extends Comparable<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;
	}

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

	@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);
		}
	}


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

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

	/**
	 * Remove. This version is longer than some other versions, but more easily
	 * understood.
	 * 
	 * @param element the element to be removed
	 * @return the payload of the node being removed, or null if the node is not found (Note that the non-null object retured, while equal to the object passed as toBeRemoved, may not be == to toBeRemoved so the return value can be interesting.)
	 */
	public E remove(E element) {
		if (root == null)
			return null;
		return removeUtil(root, null, element);
	}

	/**
	 * 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
	 */
	protected E minKey(Node<E> sRoot) {
		if (sRoot.left == null)
			return sRoot.payload;
		else
			return minKey(sRoot.left);
	}

	/**
	 * 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 the payload of the node being removed, or null if the node is not found (Note that the non-null object retured, while equal to the object passed as toBeRemoved, may not be == to toBeRemoved so the return value can be interesting.)
	 */
	private E removeUtil(Node<E> treepart, Node<E> parent, E toBeRemoved) {
		System.out.println("REM" + treepart + "   " + toBeRemoved);
		if (treepart == null)
			return null;
		int cmp = treepart.payload.compareTo(toBeRemoved);
		System.out.println("REM" + treepart + "   " + toBeRemoved + "  " + cmp);
		if (cmp > 0) {
			System.out.println(toBeRemoved + " is less than " + treepart.payload + " so left in tree");
			return removeUtil(treepart.left, treepart, toBeRemoved);
		} else if (cmp < 0) {
			System.out.println(toBeRemoved + " is greater than " + treepart.payload + " so right in tree");
			return removeUtil(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 treepart.payload;
			}
			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 treepart.payload;
			}
			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 treepart.payload;
			}
			// case 4: Two children
			E tmp = treepart.payload;
			E pred = minKey(treepart.right);
			removeUtil(treepart.right, treepart, pred);
			treepart.payload = pred;
			return tmp;
		}

	}

	@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 + "]");
	}

	// use a stack rather than recursion!!
	public String toString() {
		ArrayStack<Node<E>> as = new ArrayStack<>();
		as.push(root);
		StringBuffer sb = new StringBuffer();
		while (!as.isEmpty()) {
			Node<E> nd = as.pop();
			sb.append(nd.payload.toString());
			sb.append("  ");
			if (nd.right != null)
				as.push(nd.right);
			if (nd.left != null)
				as.push(nd.left);
		}
		return sb.toString();
	}

	@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 static void main(String[] args) {
		LinkedBinaryTree<String> ts = new LinkedBinaryTree<>();
		ts.insert("a");
		ts.insert("s");
		ts.insert("d");
		ts.insert("f");
		ts.insert("g");
		ts.insert("h");
		ts.insert("j");
		ts.insert("k");
		ts.insert("l");
		ts.insert("z");
		ts.printPostOrder();
		System.out.println(ts.toString());
		ts.remove("s");
		System.out.println(ts.toString());
		ts.remove("a");
		System.out.println(ts.toString());
		ts.remove("z");
		System.out.println(ts.toString());
		
	}
}