package lecture12;


public class BinaryTree <K extends Comparable<? super K>, D> {
	private class TreeNode {
		K key;
		D data;
		TreeNode left, right;
		TreeNode(K k, D d, TreeNode l, TreeNode r) {
			key = k; data = d; left = l; right = r;
		}
	}

	TreeNode root = null;

	void insertRecursive (K key, D data) {
		root = insertHelper (key, data, root);
	}

	TreeNode insertHelper (K key, D data, TreeNode subtree) {
		if (subtree == null)
			return new TreeNode (key, data, null, null);
		int comparisonResult = key.compareTo(subtree.key);
		if (comparisonResult < 0) // key < subtree.key
			subtree.left =  insertHelper (key, data, subtree.left);
		else if (comparisonResult > 0) // key > subtree.key
			subtree.right =  insertHelper (key, data, subtree.right);
		// if comparisonResult == 0, do nothing to avoid duplicate keys

		return subtree;
	}

	boolean insertIterative (K key, D data) {
		if (root == null) // empty tree
			root = new TreeNode (key, data, null, null);
		else {
			TreeNode current = root, parent;
			int comparisonResult;
			do {
				parent = current;
				comparisonResult = key.compareTo(current.key);
				if (comparisonResult < 0) // key < current.key
					current = current.left;
				else if (comparisonResult > 0) // key > current.key
					current = current.right;
				else // if == 0 -- do nothing to avoid duplicate nodes
					return false;
			} while (current != null);
			TreeNode newNode = new TreeNode (key, data, null, null);
			if (comparisonResult<0)
				parent.left = newNode;
			else
				parent.right = newNode;
		}
		return true;
	}

	boolean delete (K key) {
		if (root == null)
			return false;
		TreeNode current = root, parent = null;
		int comparisonResult;
		do {
			comparisonResult = key.compareTo(current.key);
			if (comparisonResult < 0) { // key<current.key
				parent = current;
				current = current.left;
			}
			else if (comparisonResult > 0) { // key>current.key
				parent = current;
				current = current.right;
			}
			else // if == 0, we found what we were looking for -- key==current.key
				break;
		} while (current != null);

		if (current == null) // not found
			return false;

		TreeNode nodeToDelete;
		if (current.right!=null && current.left != null) { // case III: two children
			nodeToDelete = current.right;
			parent = current;
			while (nodeToDelete.left != null) {
				parent = nodeToDelete;
				nodeToDelete = nodeToDelete.left;
			}
			// Now nodeToDelete is the inorder successor of current
			// parent is the parent of nodeToDelete
			current.key = nodeToDelete.key;
			current.data = nodeToDelete.data;
		}
		else 
			nodeToDelete = current;

		// Now we are in case I or II: nodeToDelete has at most 1 child
		TreeNode childToSave = nodeToDelete.right==null ? nodeToDelete.left : nodeToDelete.right;
		if (parent == null)
			root = childToSave;
		else {
			if (parent.left == nodeToDelete)
				parent.left = childToSave;
			else // parent.right == nodeToDelete
				parent.right = childToSave;
		}
		return true;
	}
}