// Traditional-style implementation of trees.  Except for the 
// Comparable<T> interface, there is no meaningful use of modern OOP features.

class node<T extends Comparable<T>>
{
    protected T item;   // value stored at node
    protected node<T> left;
    protected node<T> right;

    // accessors
    public T item() { return item; }
    public node<T> left() { return left; }
    public node<T> right() { return right; }

    // constructors:
    public node(T h, node<T> l, node<T> r) {item=h; left=l; right=r;}
    public node(T h) { item=h;  left = right = null;}

    // size function
    public int size()
    {
	int lsize = 0, rsize = 0;
	if (left!=null) lsize = left.size();
	if (right!=null) rsize = right.size();
	return lsize + rsize + 1;
    }
    
    // functional-programming style version:
    public static int size(node N)
    {
	if (N==null) return 0; else return size(N.left) + size(N.right) + 1;
    }

    // insert into binary search tree:
    // compare x with item, go left or right until null spot found:
    public void insert(T x)
    {
	node<T> current = this;
	while (current!=null)
	    {
		if (x.compareTo(item)<=0) // go left
		    {
			if (current.left==null) // insert here
			    { current.left =new node<T>(x); current=null; }
			else current = current.left;
		    }
		else // go right
		    {
			if (current.right==null) // insert here
			    {current.right = new node<T>(x); current=null; }
			else current = current.right;
		    }
	    }//while
    }//insert

    // recursive version of insert
    public void rinsert(T x)
    {
	if (x.compareTo(item)<=0) // go left
	    {
		if (left==null) left = new node<T>(x);
		else left.rinsert(x);
	    }
	else // go right
	    {
		if (right==null) right = new node<T>(x);
		else right.rinsert(x);
	    }
    }

    public boolean binsearch(T x)
     {
	/* earthling version: 
	if (item==x) return true;
	else 
	    if (item>x && left!=null) // go left
		return left.binsearch(x);
	    else 
		if (right!=null) return right.binsearch(x);
	        else return false;
	*/
	/* declarative version: */

	 return (item.compareTo(x)==0) ||
	     (item.compareTo(x)>0 && left!=null && left.binsearch(x)) ||
	     (right!=null && item.compareTo(x)<0 && right.binsearch(x));

     }//binsearch

   public void inorder()
    {
	if (left!=null) left.inorder();
	System.out.print(this.item+ " ");
	if (right!=null) right.inorder();
    }

   /* delete? well, let's try ...
      Algorithm: find node to be deleted, then:
      if left tree is null, replace node with right tree.
      if left tree is not null, 
         find and delete the largest (rightmost) node on the left tree
         and replace value at node to be deleted with largest value
         on left tree.
      Can try to use recursion to simplify implementation, but
      using a more advanced OOP design can simplify the code further...
   */
} // node

public class traditional
{
    public static void main(String[] args)
    {
	node<Integer> t1 = new node<Integer>(6,new node<Integer>(3),null);
	t1.insert(8);
	t1.rinsert(1);
	System.out.println(t1.size());
	System.out.println(node.size(t1));
	System.out.println(t1.binsearch(5));
    }
}