package class7_3_Trees_start;

import java.util.List;

public class BinarySearchTree<E extends Comparable<E>>
            extends BinaryTree<E>
            implements SearchTree<E> {

    private boolean addReturnValue = false;

    public int height() {
        return height(root);
    }

    private int height(Node root) {
        if(root == null) {
            return 0;
        }
        return 1 + Math.max(height(root.left), height(root.right));
    }


    /**
     * Inserts item where it belongs in the tree.
     *
     * @param item The item to be inserted
     * @return true If the item is inserted, false if the item was already in
     * the tree.
     */
    @Override
    public boolean add(E item) {
        root = add(root, item);
        return addReturnValue;
    }

    /**
     * Add an item to a sub-tree.
     * Sets addReturnValue to true if successful,
     * false if unsuccessful
     * @param localRoot the root of the sub-tree to add the item to
     * @param item the item to be added to the sub-tree
     * @return the new root of the tree
     */
    private Node add(Node localRoot, E item) {
        if(localRoot == null) {
            localRoot = new Node();
            localRoot.value = item;
            addReturnValue = true;
        }
        if(item.compareTo(localRoot.value)<0) {
            localRoot.left = add(localRoot.left,item);
        } else if(item.compareTo(localRoot.value)>0) {
            localRoot.right = add(localRoot.right,item);
        } else { // localRoot.equals(item)
            addReturnValue = false;
        }

        return localRoot;
    }

    /**
     * Determine if an item is in the tree
     *
     * @param target Item being sought in tree
     * @return true If the item is in the tree, false otherwise
     */
    @Override
    public boolean contains(E target) {
        return find(target) != null;
    }

    public E find(E element) {
        return find(root,element);
    }

    /**
     * Removes target from tree.
     *
     * @param target Item to be removed
     * @return A reference to the object in the tree that compares equal as
     * determined by compareTo to the target. If not found null is returned.
     * @post target is not in the tree
     */
    @Override
    public E delete(E target) {
        throw new UnsupportedOperationException();
    }

    /**
     * Removes target from tree.
     *
     * @param target Item to be removed
     * @return true if the object was in the tree, false otherwise
     * @post target is not in the tree
     */
    @Override
    public boolean remove(E target) {
        throw new UnsupportedOperationException();
    }

    /**
     * Return a list containing the contents of the search tree in ascending
     * order.
     *
     * @return a list containing the contents of the search tree in ascending
     * order.
     */
    @Override
    public List<E> toList() {
        throw new UnsupportedOperationException();
    }

    /**
     * Empty this SearchTree
     */
    @Override
    public void clear() {
        throw new UnsupportedOperationException();
    }

    private E find(Node localRoot, E element) {
        if(localRoot == null) {
            return null;
        } else {
            if(element.compareTo(localRoot.value)<0) {
                return find(localRoot.left,element);
            } else if(element.compareTo(localRoot.value)>0) {
                return find(localRoot.right,element);
            } else {
                return localRoot.value;
            }
        }
    }
}