/* binary tree class */

interface tree
{
    int size();  // number of nodes in tree
    node lookup(int x); // search for x in tree, return null if not found
}

class nil implements tree
{
    public int size() {return 0;}
    public node lookup(int x)
    {
	if (head==x) return this;
	node n = left.lookup(x);
	if (n==null) n = right.lookup(x);
	return n; 
    }
    public String toString() { return ""; }
    public static final nil NIL = new nil();
}

class node implements tree
{
    int head; // data stored in node
    tree left, right;
    public node(int h, tree l, tree r)
    { head=h; left=l; right=r; }

    public int size()
    { return left.size() + right.size() + 1; }
    public String toString()
    { return left.toString()+head+" "+right.toString(); }
} // node


/*           ******************          */


// The following aspect implements binary search trees, with a 
// new signature

interface searchtree
{
    boolean isbst(int min, int max);  // check if tree is a search tree
    node insert(int x);  // insert x, return new tree
    bstlookup(int x);
}

aspect bst
{

    // modify inheritance hierarchy (locally);
    declare parents : tree extends searchtree;

    // boolean var to indicate that 
    
    // define new methods for each class tree:
    public node nil.bstlookup(int x) { return null; }
    public node node.bstlookup(int x) 
	{ 
	    if (x==head) return this;
	    else if (x<head) return left.lookup(x);
	    else return right.lookup(x);
	}
    
    public tree nil.insert(int x)
        { return new node(x,this,this); }
    public tree node.insert(int x)
	{
	    if (x<=head) left=left.insert(x);
	    else right=right.insert(x);
	    return this;
	}

    public boolean nil.isbst(int min, int max)
        { return true; }
    public boolean node.isbst(int min, int max)
	{  
	    return (min <=head && head<max &&
      	            left.isbst(min,head) && right.isbst(head,max));
	}

    // advice to 

    public static void test()  // to be called from main
	{
	    tree A = nil.NIL;
	    A = A.insert(6);
	    A.insert(3);   // know A is not nil
	    A.insert(8);
	    A.insert(4);
	    System.out.println(A);
	}

} // bst aspect


// test
public class ints
{
    public static void main(String[] argv)
    {
	bst.test();
    }
} // ints