package treesbinary;

public class Node {
    int key;
    String name;
    Node leftChild;
    Node rightChild;

    Node (int key, String name) {
        this.key = key;
        this.name = name;
    }

    public String toString() {
        return name + " has the key " + key;
    }
}

package treesbinary;

public class BinaryTreeComplete {
    Node root;

   public  void addNode(int key, String name) {
       Node newNode = new Node(key, name);
       if(root == null) {
           root = newNode;
       }
       else {
           Node focusNode = root;
           Node parent;
           while (true) {
               parent = focusNode;
               if(key < focusNode.key) {
                   focusNode = focusNode.leftChild;
                   if (focusNode == null) {
                       parent.leftChild = newNode;
                       return;
                   }
               }
               else {
                   focusNode = focusNode.rightChild;
                   if(focusNode == null) {
                       parent.rightChild = newNode;
                       return;
                   }
               }
           }
       }
   }

   public void inOrderTraverseTree(Node focusNode) {
       if(focusNode != null) {
           inOrderTraverseTree(focusNode.leftChild);
           System.out.println(focusNode);
           inOrderTraverseTree(focusNode.rightChild);
       }
   }

    public void preOrderTraverseTree(Node focusNode) {
        if(focusNode != null) {
            System.out.println(focusNode);
            preOrderTraverseTree(focusNode.leftChild);
            preOrderTraverseTree(focusNode.rightChild);
        }
    }

    public void postOrderTraverseTree(Node focusNode) {
        if(focusNode != null) {
            postOrderTraverseTree(focusNode.leftChild);
            postOrderTraverseTree(focusNode.rightChild);
            System.out.println(focusNode);
        }
    }

    public Node findNode(int key) {
       Node focusNode = root;
       while(focusNode.key != key) {
           if(key < focusNode.key) {
               focusNode = focusNode.leftChild;
           }
           else {
               focusNode = focusNode.rightChild;
           }
           if(focusNode == null) {
               return null;
           }
       }
       return focusNode;
    }

    public boolean remove(int key) {
        Node focusNode = root;
        Node parentNode = root;
        //Start search for key on the leftChild
        boolean isItALeftChild = true;
        //Keep looking for the search Node
        while(focusNode.key != key) {
            parentNode = focusNode;
            //Search left?
            if(key < focusNode.key) {
                isItALeftChild = true;
                focusNode = focusNode.leftChild;
            }
            else {
                //Searching to the Right
                isItALeftChild = false;
                focusNode = focusNode.rightChild;
            }
            //Node not found
            if(focusNode == null) {
                return false;
            }
        }
        //Node with no children DELETE IT!
        if(focusNode.leftChild == null && focusNode.rightChild == null) {
            //If it is the Root and has no children DELETE IT!
            if(focusNode == root) {
                root = null;
            }
            //If it is marked as a Left Child of the Parent
            //Then DELETE it in the Parent
            else if(isItALeftChild) {
                parentNode.leftChild = null;
            }
            //If it is marked as a Right Child of the Parent
            //Then DELETE it in the Parent
            else {
                parentNode.rightChild = null;
            }
        }
        //If Node has no Right Child
        else if (focusNode.rightChild == null) {
            if (focusNode == root)
                root = focusNode.leftChild;
                // If focus Node was on the left of parent
                // move the focus Nodes left child up to the
                // parent node
            else if (isItALeftChild)
                parentNode.leftChild = focusNode.leftChild;
                // Vice versa for the right child
            else
                parentNode.rightChild = focusNode.leftChild;
        }
        // If no left child
        else if (focusNode.leftChild == null) {
            if (focusNode == root)
                root = focusNode.rightChild;
                // If focus Node was on the left of parent
                // move the focus Nodes right child up to the
                // parent node
            else if (isItALeftChild)
                parentNode.leftChild = focusNode.rightChild;
                // Vice versa for the left child
            else
                parentNode.rightChild = focusNode.rightChild;
        }
        // Two children so I need to find the deleted nodes
        // replacement
        else {
            Node replacement = getReplacementNode(focusNode);
            // If the focusNode is root replace root
            // with the replacement
            if (focusNode == root)
                root = replacement;
                // If the deleted node was a left child
                // make the replacement the left child
            else if (isItALeftChild)
                parentNode.leftChild = replacement;
                // Vice versa if it was a right child
            else
                parentNode.rightChild = replacement;
            replacement.leftChild = focusNode.leftChild;
        }
        return true;
    }

    public Node getReplacementNode(Node replacedNode) {
        Node replacementParent = replacedNode; //Example 15
        Node replacement = replacedNode; //Example 15
        Node focusNode = replacedNode.rightChild; //Example 18
        // While there are no more left children
        while (focusNode != null) {
            replacementParent = replacement;//Example 15 - 18
            replacement = focusNode;//Example 18 - 16
            focusNode = focusNode.leftChild;//Example 16 - null
        }
        // If the replacement isn't the right child
        // move the replacement into the parents
        // leftChild slot and move the replaced nodes
        // right child into the replacements rightChild
        if (replacement != replacedNode.rightChild) {
            replacementParent.leftChild = replacement.rightChild;
            replacement.rightChild = replacedNode.rightChild;
        }
        return replacement;
    }
}

package treesbinary;

public class BinaryTestDeleteDemo {
    public static void main(String[] args) {
        BinaryTreeComplete  binaryTreeComplete= new BinaryTreeComplete();
        binaryTreeComplete.addNode(50, "Vice Chancellor");
        binaryTreeComplete.addNode(25, "Dean of Faculty");
        binaryTreeComplete.addNode(15, "Faculty Manager");
        binaryTreeComplete.addNode(30, "Faculty Secretary");
        binaryTreeComplete.addNode(18, "Another Faculty Manager");
        binaryTreeComplete.addNode(75, "Head of School");
        binaryTreeComplete.addNode(80, "Senior Lecturer");
        binaryTreeComplete.addNode(2, "Building Manager");
        binaryTreeComplete.addNode(16, "Library Manager");
        System.out.println("Binary Tree In Order Traversal");
        binaryTreeComplete.inOrderTraverseTree(binaryTreeComplete.root);
        System.out.println("==========================================================");
        System.out.println("Binary Tree Preorder Traversal");
        binaryTreeComplete.preOrderTraverseTree(binaryTreeComplete.root);
        System.out.println("==========================================================");
        System.out.println("Binary Tree Post order Traversal");
        binaryTreeComplete.postOrderTraverseTree(binaryTreeComplete.root);

        System.out.println("\nNode with the key 75");
        System.out.println(binaryTreeComplete.findNode(75));

        //binaryTreeComplete.remove(80);
        //binaryTreeComplete.remove(75);
        //binaryTreeComplete.remove(16);
        binaryTreeComplete.remove(25);

        System.out.println("Binary Tree In Order Traversal");
        binaryTreeComplete.inOrderTraverseTree(binaryTreeComplete.root);
    }
}
//Reference
//http://www.newthinktank.com/2013/03/binary-trees-in-java-2/