/* T06n01 - A demonstration of recursive insertion into a binary search tree.
 * (Obviously, this is a very incomplete implementation; the idea is to show
 * enough to make the points we need to make.)
 *
 * The representation is recursive:  A tree is a data value and two other
 * trees (the left and right subtrees).  This matches well with the usual
 * recursive definition of a binary tree.  Matches well, but not perfectly,
 * as we point out below.  Because this implementation adopts the
 * philosophy that trees are built of trees, there are no nodes.
 *
 * The point of this example is to show one way to add data
 * to a binary tree.  The algorithm is straight-forward:  We insert a new
 * value into either the tree's left subtree or its right subtree, based
 * on the result of the comparison.  If the subtree into which we need to
 * insert doesn't exist, we'll create a subtree to hold the new data item
 * and add it to the tree's fringe.  Otherwise, we pass off the new data
 * to the subtree and let it deal with it.
 *
 * To make the tree generally useful, we've written it to hold Comparable
 * object references, instead of a specific base type, a specific object
 * reference, or references to generic Objects.  Because items are placed
 * within a BST according to the BST ordering property, we need to be
 * able to compare tree data items.  By making the items Comparable, we
 * have a uniform way to make our comparisons (specifically, the compareTo()
 * method that all Comparable objects implement), and thus we can build
 * trees that store any Comparable objects.
 *
 * Note that there really isn't the possibility of an empty tree in this
 * implementation.  Sure, the application's reference is set to null
 * initially, but you can't send a message to a null reference. If
 * a null tree is a tree, you ought to be able to traverse it, for example.
 */

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

public class T06n01
{
    public static void main (String[] args)
    {
        BinarySearchTree tree = null;

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

class BinarySearchTree
{
    private BinarySearchTree leftSubTree, 
                             rightSubTree;
    private Comparable       data;        


    public BinarySearchTree (Comparable initialData)
    {
        data = initialData;
        leftSubTree = rightSubTree = null;
    }

    public void insert (Comparable newData)
    {
        if (newData.compareTo(data) < 0) {
            if (leftSubTree != null) {
                leftSubTree.insert(newData);
            } else {
                leftSubTree = new BinarySearchTree(newData);
            }
        } else {
            if (rightSubTree != null) {
                rightSubTree.insert(newData);
            } else {
                rightSubTree = new BinarySearchTree(newData);
            }
        }
    } 

    public void inOrder ()
    {
        if (leftSubTree != null) { leftSubTree.inOrder(); }
        System.out.print(data.toString() + " ");
        if (rightSubTree != null) { rightSubTree.inOrder(); }
    }
}