package class6_2_BinarySearchTree;

public class BinarySearchTree<E extends Comparable<E>> {
    Node root;

    private class Node {
        Node left;
        Node right;
        E value;

        private Node(Node left, Node right, E value) {
            this.left = left;
            this.right = right;
            this.value = value;
        }
    }

    public void add(E e) {
        if(root == null) {
            root = new Node(null, null, e);
        } else {
            add(e, root);
        }
    }

    /**
     * @param e value to add
     * @param current the root of the sub-tree to add the node under
     *                current != null
     */
    private void add(E e, Node current) {
        if(e.compareTo(current.value) < 0 && current.left == null
             || e.compareTo(current.value) >=0 && current.right == null) {
            Node newNode = new Node(null, null, e);
            if(e.compareTo(current.value) < 0) {
                current.left = newNode;
            } else {
                current.right = newNode;
            }
        } else {
            if(e.compareTo(current.value) < 0) { // e < current
                // BUG: Should not check again (as below).  Should just go left or right
                // based on the result of the if above.
                if(e.compareTo(current.value) < 0) {
                    add(e, current.left);
                } else {
                    add(e, current.right);
                }
            }
        }
    }

    public void oldAdd(E e) {
        Node newNode = new Node(null, null, e);

        if(root == null) {
            root = newNode;
        } else {
            Node current = root;
            Node prev = null;
            while(current != null) {
                if(e.compareTo(current.value) < 0) { // e < current
                    prev = current;
                    current = current.left;
                } else {
                    prev = current;
                    current = current.right;
                }
            }
            if(e.compareTo(prev.value) < 0) {
                prev.left = newNode;
            } else {
                prev.right = newNode;
            }
        }
    }

    public void print() {
        printTree(root, 0);
    }

    private void printTree(Node current, int depth) {
        if(current != null) {
            printTree(current.left,depth+1);
            for(int i=0;i<depth;i++) {
                System.out.print(" ");
            }
            System.out.println(current.value);
            printTree(current.right,depth+1);
        }
    }
}