/* T15n01 - A traditional (but incomplete) implementation of a binary search
 * tree class.  Note the parallels with linked lists -- we have a class
 * for the data structure (BinarySearchTree) and one for the components
 * of the structure (BinaryNode).
 *
 * If you're into OO design, you might be annoyed by the use
 * of nulls to mark the fringe of the tree.  If so, see the next
 * example.  If not, see it anyway; you need to see the idea whether you
 * find nulls to be evil or not.
 */

import java.io.*;
import java.util.*;

public class T15n01
{
    public static void main (String[] args)
    {
        BinarySearchTree<Integer> tree = null;

        tree = new BinarySearchTree<Integer>();
        tree.insert(50);
        tree.insert(40);
        tree.insert(60);
        tree.insert(45);
        tree.insert(42);
        tree.inOrder();
        System.out.println("");
    }
}

        /*  The funky "BinarySearchTree< E extends Comparable<E> >" class
         *  header deserves some explanation.  We're creating a BST, which
         *  means that the data stored within the tree needs to be compared
         *  so that we know when a match is found, or whether or not a
         *  value is larger or smaller than another.  To do
         *  that, we must ensure that the data class supports the Comparable
         *  interface (else we can't be sure that compareTo()
         *  is available).  Java allows us to write the header with a
         *  qualification to accept only type arguments that are known to 
         *  extend Comparable.  And, of course, Comparable itself is
         *  parameterized, so we need the "<E>" on it, too.
         */

class BinarySearchTree< E extends Comparable<E> >
{
    protected BinaryNode<E> root;

    public BinarySearchTree ()
    {
        root = null;
    }

    public void insert (E newData)
    {
        root = insert(root, newData);
    }

    private BinaryNode<E> insert (BinaryNode<E> node, E newData)
    {
        if (node == null) {              // need to create a new subtree
            return new BinaryNode<E>(newData);
        } else if (newData.compareTo(node.data) < 0) {   // insert on left
            node.leftChild = insert(node.leftChild, newData); 
        } else {                                         // insert on right
            node.rightChild = insert(node.rightChild, newData);
        }
        return node;
    } 

    public void inOrder ()
    {
        inOrder(root);
    }

    private void inOrder (BinaryNode<E> node)
    {
        if (node != null) {
            inOrder(node.leftChild);
            System.out.print((node.data).toString() + " ");
            inOrder(node.rightChild);
        }
    }


    class BinaryNode<E>
    {
        E             data;       
        BinaryNode<E> leftChild,  
                      rightChild; 

        public BinaryNode (E newData)
        {
            data = newData;
            leftChild = rightChild = null;
        }
    }

}