package chapter17;

//*******************************************************************
//  LinkedBinarySearchTree.java       Java Foundations
//
//  Implements the binary tree using a linked representation.
//*******************************************************************

import chapter16.BTNode;
import chapter16.LinkedBinaryTree;

public class LinkedBinarySearchTree<T extends Comparable<T>> extends LinkedBinaryTree<T> implements BinarySearchTree<T>
{
    //-----------------------------------------------------------------
    //  Creates an empty binary search tree.
    //-----------------------------------------------------------------
    public LinkedBinarySearchTree()
    {
        super();
    }

    //-----------------------------------------------------------------
    //  Creates a binary search tree with the specified element at its
    //  root.
    //-----------------------------------------------------------------
    public LinkedBinarySearchTree (T element)
    {
        root = new BSTNode<T>(element);
    }

    //-----------------------------------------------------------------
    //  Adds the specified element to this binary search tree.
    //-----------------------------------------------------------------
    public void add (T item)
    {
        if (root == null)
            root = new BSTNode<T>(item);
        else
            ((BSTNode)root).add(item);
    }

    //-----------------------------------------------------------------
    //  Removes and returns the element matching the specified target
    //  from this binary search tree. Throws an ElementNotFoundException
    //  if the target is not found.
    //-----------------------------------------------------------------
    public T remove (T target) throws Exception {
        BSTNode<T> node = null;

        if (root != null)
            node = ((BSTNode)root).find(target);

        if (node == null)
            throw new Exception ("Remove operation failed. "
                    + "No such element in tree.");

        root = ((BSTNode)root).remove(target);

        return node.getElement();
    }

    //-----------------------------------------------------------------
    //  The following methods are left as programming projects.
    //-----------------------------------------------------------------
     public T findMin() {
        BTNode<T> r =  root;
        while (r.getLeft() != null)
            r = r.getLeft();
        return  r.getElement();
     }
     public T findMax() {
         BTNode<T> r =  root;
        while (r.getRight() != null)
            r = r.getRight();
        return  r.getElement();
     }

}