/*
 * Implementation for the dictionary with a BinarySearchTree
 *
 * Restrict your changes to the bottom of the file, and be sure your
 *   operations run in the specified time.
 * Take advantage of the tree printing methods provided when testing
 */
public class BinarySearchTree implements Dictionary {

  /*
   * This is the pointer to the start of the tree.
   * If root is null, then the tree is empty.
   */
	protected TreeNode root;

  /*
   * The number of keys in the tree
   */
	protected int numNodes;

	public BinarySearchTree() {
		root = null;
		numNodes = 0;
	}

  /*
   * Testing Aid provided for you...
   *
   * Print out the nodes of the tree in an inorder traversal.  One entry
   * is printed per line.
   */
	public void inOrderPrint() {
		System.out.println("Inorder Traversal:");
		if (root == null) {
			System.out.println("empty tree");
		} else {
			root.inOrderPrint();
		}
	}

  /*
   * Testing Aid provided for you...
   *
   * Print out the nodes of the tree in a preorder traversal.  One entry
   * is printed per line.
   */
	public void preOrderPrint() {
		System.out.println("Preorder Traversal:");
		if (root == null) {
			System.out.println("empty tree");
		} else {
			root.preOrderPrint();
		}
	}

  /*
   * Testing Aid provided for you...
   *
   * Print out the nodes of the tree in an inorder traversal.
   *   The root node will be printed out with 0 spaces
   *   in front of it.  The immediate children will be printed out with
   *   four extra spaces in front of it.  Their children will be printed out
   *   with four more extra spaces in front of it... and so on.
   * This should make checking your tree a little easier to visualize.
   */
	public void inOrderPrintDepth() {
		System.out.println("Inorder Traversal with depths:");
		if (root == null) {
			System.out.println("empty tree");
		} else {
			root.inOrderPrintDepth(0);
		}
	}

/*******************************************************************/
/* Restrict your changes to BELOW this line to ensure you do not   */
/* lose any marks unneccessarily.                                  */
/*******************************************************************/

  /*
   * You need to implement this in O(1) time
   */
	public int dictionaryLength() {
		return numNodes;
	}

  /*
   * Create a new entry in the tree preserving the sorted binary property.
   * You need to implement this in O(h) where h is the height of the tree.
   */
	public void insert(int key, String data) {
		int iteratorKey = 0;
		TreeNode tmpRoot = null;
		TreeNode iterator = null;
		TreeNode treeNode = new TreeNode(key, data);

		if (root == null) {
			root = treeNode;

			// Increment number of nodes
			numNodes++;
		} else {
			// Traverse tree, starting at root till element found or added
			iterator = root;
			while (true) {
				// Keep track parent node
				tmpRoot = iterator;
				iteratorKey = iterator.getKey();

				// Key already exist, replace
				if (iteratorKey == key) {
					iterator.setData(data);
					return;
				} else if (key < iteratorKey) {
					// Go left
					iterator = iterator.getLeft();

					// We're at the end of left the branch
					if (iterator == null) {
						tmpRoot.setLeft(treeNode);

						// Increment number of nodes
						numNodes++;

						// We're done
						return;
					}
				} else if (key > iteratorKey) {
					// Go right
					iterator = iterator.getRight();

					// We're at the end of right branch
					if (iterator == null) {
						tmpRoot.setRight(treeNode);

						// Increment number of nodes
						numNodes++;

						// We're done
						return;
					}
				}
			}
		}
	}

  /*
   * You need to implement this in O(h) where h is the height of the tree.
   */
	public boolean delete(int searchKey) {
        TreeNode iterator = root;
        TreeNode tmpRoot = null;
        int iteratorKey = 0;
        boolean isLeftTree = false;

        // Look for searchKey
        iteratorKey = iterator.getKey();
        while (iteratorKey != searchKey) {
            // Kep track of parent node
            tmpRoot = iterator;

			if (searchKey < iteratorKey) {
                iterator = iterator.getLeft();

                // Keep track of which direction we are going
                isLeftTree = true;
            } else if (searchKey > iteratorKey) {
                iterator = iterator.getRight();

                // Keep track of which direction we are going
                isLeftTree = false;
            }

            // We found the end of the tree (left side or right side)
            // and searchKey is not in the tree
            if (iterator == null) {
                return false;
            }

            // Get next node's key value
            iteratorKey = iterator.getKey();
        }

        // Delete the node
		return doDeleteNode(tmpRoot, iterator, isLeftTree );
	}

    /**
     * Delete node.
     * There are three cases to take into account:
     * 1. Node doesn't have any children
     * 2. Node has either left or right child
     * 3. Node has left and right children
     * @param tmpRoot Parent of node delete
     * @param iterator The node to delete
     * @param isLeftRTree Flag to indicate which subtree we are in
     * @return boolean
     */
    private boolean doDeleteNode(TreeNode tmpRoot, TreeNode iterator, boolean isLeftTree) {
        // 1. No children, then delete node
        if ((iterator.getLeft() == null) && (iterator.getRight() == null)) {
            // Is the node root
            if (iterator == root) {
                root = null;
            } else if (isLeftTree) {
                // Exterior node to delete is in the left side
                tmpRoot.setLeft(null);
            } else {
                // Otherwise, the node to delete is in the rigt side
                tmpRoot.setRight(null);
            }
        } else if(iterator.getRight() == null) {
            // 2.i. There is a left child, but, no right one
            // If we delete root, then attach to it's left child
            if (iterator == root) {
                root = iterator.getLeft();
            } else if (isLeftTree) {
                // Node is a left child
                tmpRoot.setLeft(iterator.getLeft());
            } else {
                // Node is a right child
                tmpRoot.setRight(iterator.getLeft());
            }
        } else if (iterator.getLeft() == null) {
            // 2.ii. There is a right child, but, no left one
            // If root, then it's a special case
            if (iterator == root) {
                root = iterator.getRight();
            } else if (isLeftTree) {
                tmpRoot.setLeft(iterator.getRight());
            } else {
                tmpRoot.setRight(iterator.getRight());
            }
        } else {
            // 3. Node has two children
            // We delete by swaping with inorder successor
            // Go to the left subtree and find the right most node

             // Tree to traverse
            TreeNode iterator2 = iterator.getLeft();

            // Root of traversee
            TreeNode tmpRoot2 = iterator;

            // Parent of root while being traversed
            TreeNode tmpRoot2Parent = iterator;

            // Loop until the right most node has been found
            while (iterator2 != null) {
                tmpRoot2Parent = tmpRoot2;
                tmpRoot2 = iterator2;
                iterator2 = iterator2.getRight();
            }

            // Swap value of innermost successor
            iterator.setKey(tmpRoot2.getKey());
            iterator.setData(tmpRoot2.getData());

            // Reattach trees if any
            if (tmpRoot2Parent == iterator) {
                // If right most tree is the immediate left tree of the node
                // If children has a subtree, re-attach
                if (tmpRoot2.getLeft() != null) {
                    tmpRoot2Parent.setLeft(tmpRoot2.getLeft());
                } else {
	                tmpRoot2Parent.setLeft(null);
                }
            } else if (tmpRoot2.getLeft() != null) {
                // Rightmost tree has a left child, hence,
                // attach to main tree
                tmpRoot2Parent.setRight(tmpRoot2.getLeft());
            } else {
            	// Delete node
            	tmpRoot2Parent.setRight(null);
            }
        }

        // We have deleted a node, hence decrement by one
        numNodes--;

        // We have successfuly deleted the required node hence return true
        return true;
    }

  /*
   * You need to implement this in O(h) where h is the height of the tree.
   */
	public String find(int searchKey) {
		TreeNode iterator = root;
		int iteratorKey = iterator.getKey();

		// While key not found
		while (iteratorKey != searchKey) {
			// Go left, if searchKey < iteratorKey
			if (searchKey < iteratorKey) {
				iterator = iterator.getLeft();
			} else {
				iterator = iterator.getRight();
			}

			// No children, hence not found
			if (iterator == null) {
				return null;
			}

			// Get node's key
			iteratorKey = iterator.getKey();
		}

		// searchKey was found
		return iterator.getData();
	}

    // Get root
    public TreeNode getRoot() {
        return root;
    }
}