package Upg8;

import java.util.NoSuchElementException;

public class BinarySearchTree<E extends Comparable<E>> {

    private static class Node<E>{
        private E data;
        private Node<E> left, right;
        public Node(E data) {
            this.data = data;
            left = right = null;
        }
        @Override
        public String toString() {
            return data.toString();
        }
    }

    private Node<E> root;
    private E deletedData;

    public BinarySearchTree() {
        this.root = null;
        deletedData = null;
    }

    public boolean add(E data){
        if(root == null) {
            root = new Node<E>(data);
            return true;
        } else return add(data,root);
    }

    private boolean add(E data, Node<E> node) {
        if(data.compareTo(node.data) == 0)
            return false;
        else if(data.compareTo(node.data) < 0)
            if (node.left == null){
                node.left = new Node<E>(data);
                return true;
            } else return add(data, node.left);
        else
            if(node.right == null){
                node.right = new Node<E>(data);
                return true;
            } else return add(data, node.right);
    }

    public E findRec(E target){
        return findRec(target, root);
    }

    private E findRec(E target, Node<E> node){
        if(node == null) return null;
        int tmp = target.compareTo(node.data);
        if(tmp == 0)
            return node.data;
        if(tmp < 0)
            return findRec(target, node.left);
        return findRec(target,node.right);
    }

    public E findIter(E target){
        if(root == null)
            return null;
        Node<E> index = root;
        while (index != null){
            int tmp = target.compareTo(index.data);
            if(tmp == 0)
                return index.data;
            else if(tmp < 0)
                index = index.left;
            else index = index.right;
        }
        return null;
    }

    public E maxIt(){
        if(root == null)
            return null;
        Node<E> max = root;
        while (max.right != null){
            max = max.right;
        }
        return max.data;
    }

    public E maxRec(){
        if(root == null)
            return null;
        return maxRec(root);
    }

    private E maxRec(Node<E> index){
        if(index.right == null)
            return index.data;
        else return maxRec(index.right);
    }

    public E delete(E target){
        root = delete(target, root);
        return deletedData;
    }

    private Node<E> delete(E target, Node<E> node){
        if(node == null){ //Target is not in tree
            deletedData = null;
            return null;
        } else {
            if(target.compareTo(node.data)<0){ //Target is on Tree's left side
                node.left = delete(target,node.left);
                return node;
            } else if(target.compareTo(node.data)>0){ //Target in on Tree's right side
                node.right = delete(target,node.right);
                return node;
            } else { //Target finns i node
                deletedData = node.data; //Store data to return
                //Now reconstruction of the tree
                if(node.left == null) //Node to remove doesn't have left tree
                    return node.right;
                else if(node.right == null) //Node to remove doesn't have right tree
                    return node.left;
                else { //Node to remove have two children
                    Node<E> nodeToMove=node.right, parentNodeToMove=node;
                    if(nodeToMove.left==null){ //Right children have no left child
                        nodeToMove.left=node.left;
                        return nodeToMove;
                    }
                    //Right children have left children
                    while (nodeToMove.left!=null){
                        parentNodeToMove = nodeToMove;
                        nodeToMove = nodeToMove.left;
                    }
                    parentNodeToMove.left = nodeToMove.right;
                    node.data = nodeToMove.data;
                    return node;
                }
            }
        }
    }

    private void inOrder(Node<E> node, StringBuilder sb){
        if(node!=null){
            inOrder(node.left, sb);
            sb.append(": ").append(node.toString());
            inOrder(node.right, sb);
        }
    }

    private void preOrder(Node<E> node, StringBuilder sb){
        if(node!=null){
            sb.append(": ").append(node.toString());
            preOrder(node.left, sb);
            preOrder(node.right, sb);
        }
    }

    private void postOrder(Node<E> node, StringBuilder sb){
        if(node!=null){
            postOrder(node.left, sb);
            postOrder(node.right, sb);
            sb.append(": ").append(node.toString());
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        inOrder(root, sb);
        return sb.toString();
    }

    public String toStringPreOrder() {
        StringBuilder sb = new StringBuilder();
        preOrder(root, sb);
        return sb.toString();
    }

    public String toStringPostOrder() {
        StringBuilder sb = new StringBuilder();
        postOrder(root, sb);
        return sb.toString();
    }

    public static void main(String[] args) {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        bst.add(4);
        bst.add(2);
        bst.add(1);
        bst.add(3);
        bst.add(6);
        bst.add(5);
        bst.add(7);
        System.out.println("Inorder" + bst.toString());
        System.out.println("Find 3: " + bst.findRec(3));
        System.out.println("Find Iter 3: " + bst.findIter(3));
        System.out.println("Find 8 (doesn't exists) : " + bst.findIter(8));
        System.out.println("Max Iterative: " + bst.maxIt());
        System.out.println("Max Recursive: " + bst.maxRec());
    }
}