package bstrees;
import java.util.NoSuchElementException;
import java.util.Iterator;

public class BinarySearchTree<E extends Comparable<? super E>> {
	
	private static class Node<E> {	
		E data;         // The data in the node
        Node<E> left;   // Left child
        Node<E> right;  // Right child
        Node<E> parent; // Parent

        Node(E data) {
            this(data, null, null, null);
        }

        Node(E data, Node<E> left, Node<E> right, Node<E> parent) {
            this.data = data;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }  
        
        public String toString() {
        	return data.toString();
        }
    }
	
	// Inner class implementing Iterator interface
	//private class BSTreeIterator implements Iterator<E> {	
	//}
	
    /** The tree root */
    private Node<E> root;
	
    /** The size of the tree */
    private int size;
    
    /**
     * Construct an empty tree.
     */
    public BinarySearchTree {
        root = null;
        size = 0;
    }
    
    /**
     * Make the tree empty
     */
    public void clear() {
        throw new UnsupportedOperationException();
    }
    
    /**
     * @return the size of the tree.
     */
    public int size() {
    	throw new UnsupportedOperationException();
    }
    
    /**
     * Test if the tree is empty.
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty() {
    	throw new UnsupportedOperationException();
    }
    

    /**
     * Find an item in the tree.
     * @param data the item to search for.
     * @return the matching data or null if not found.
     */
    public E find(E data) {
    	throw new UnsupportedOperationException();
    }
    
    /**
     * Internal method to find an item in the tree.
     * @param data the item to search for.
     * @return node containing data or null if not found.
     */
    private Node<E> findNode (E data) {
    	throw new UnsupportedOperationException();
    }
    
    /**
     * Insert into the tree.
     * @param data the item to insert.
     * @return false if data already present.
     */
    public boolean insert(E data) {
    	Node<E> tmp = root;
    	Node<E> parent = null;
    	int compared = 0;
    	while(tmp != null) {
    		parent = tmp;
    		compared = tmp.data.compareTo(data);
    		if(compared == 0)
    			return false;
    		if(compared < 0)
    			tmp = tmp.right;
    		else
    			tmp = tmp.left;
    	}
    	tmp = new Node<E>(data, null, null, parent);
    	if(parent == null) // insert in an empty tree
    		root = tmp;
    	else if(compared < 0)
    		parent.right = tmp;
    	else
    		parent.left = tmp;
    	size++;
    	return true;
    }
    
    /**
     * Remove from the tree.
     * @param data the item to remove.
     * @throws NoSuchElementException if data not found.
     */
    public void remove(E data) {
    	throw new UnsupportedOperationException();
    }
    
    private void removeNode(Node<E> toDelete) {
    	throw new UnsupportedOperationException();
    }
    
    /**
     * Find the smallest element in the tree.
     * @return smallest element or null if tree is empty.
     */
    public E findMinimum() {
    	throw new UnsupportedOperationException();
    }
    
    /**
     * Find the largest element in the tree.
     * @return the largest element or null if tree is empty
     */
    public E findMaximum() {
    	throw new UnsupportedOperationException();
    }
    
    //public Iterator<E> iterator() {
    	//return new  BSTreeIterator();
    //}
    
    public String toString() {
    	throw new UnsupportedOperationException();
    }
    
    private String preOrder(Node<E> node, int level) { 	
    	throw new UnsupportedOperationException();
    }
}