// node class, polymorphic

public class node<Ty extends Comparable<Ty>>
{
    public Ty head;
    public node<Ty> left;
    public node<Ty> right;

    public node(Ty h, node<Ty> l, node<Ty> r)  // constructor
    { head=h; left=l; right= r; }

    public node(Ty h) { head=h; left = right = null; } // leaf constructor

    // Naturally polymorphic functions:

    // count the number of nodes in a tree: must think recursively:
    public int size()
    {
	int sizeleft = 0, sizeright= 0;
	if (left!=null) sizeleft = left.size();
	if (right!=null) sizeleft = right.size();
	return 1 + sizeleft + sizeright;
    }

    // static version (must take node as parameter)
    public static int ssize(node<?> N)  // ? means don't care
    {
	if (N==null) return 0; 
	else return 1 + ssize(N.left) + ssize(N.right);
    }

    // inorder, preorder, postorder traversal of tree
    public void preorder()
    {
	System.out.print(head);
	if (left!=null) left.preorder();
	if (right!=null) right.preorder();  // show examples.
    }
    // show examples of pre, in and post-order 
    // post order is right-left-head.

    // depth of tree (class exercise)
    public int depth() // depth of empty tree null is 0
    {
	int ldepth = 0, rdepth = 0;
	if (left!=null) ldepth = left.depth();
	if (right!=null) rdepth = right.depth();
	if (ldepth > rdepth) return ldepth+1;
	else return rdepth+1;
    }

    // count number of times element x occurs in tree
    public int occurs(Ty x)
    {
	int lc=0, rc = 0;
	if (left!=null) lc = left.occurs(x);
	if (right!=null) rc = right.occurs(x);
	if (head.compareTo(x)==0) return 1+ lc + rc;
	else return lc+rc;
    }
    
    // print all nodes on level n of tree: - pre-order (left-to-right)
    private void printlevel(int n)
    {
	if (n<=0) // base case - print head
	    System.out.print(head + "\t");
	else 
	    {
		if (left!=null) left.printlevel(n-1);
		if (right!=null) right.printlevel(n-1);
	    }
    }//printlevel

    // print tree level by level:
    public void printbylevel()
    {
	int d = this.depth(); //compute depth of tree - number of levels
	for (int i =0;i<=d; i++)
	    {
		printlevel(i); 
		System.out.println(); // newline
	    }
    }//printbylevel


    // checking if tree is indeed a BST:
    // recursive invariance: min<head, head<=max
    private boolean isbst(Ty min, Ty max)
    {
	// null is treated as both - and + infinity
	if ((min!=null && min.compareTo(head)>=0) ||
	    (max!=null && head.compareTo(max)>0)) return false;
	else
	    {
		return (left==null || left.isbst(min,head)) &&
		       (right==null || right.isbst(head,max));
	    }
	//return (min==null || min.compareTo(head)<0) &&
	// (max==null || head.compareTo(max)<=0) &&
	// (left==null || left.isbst(min,head)) &&
	// (right==null || right.isbst(head,max);
    }

    public boolean checkbst() { return isbst(null,null); }


    ///////////////////// Spanning Tree /////////////////////////

    // How do we know that a tree is really a tree?
    public boolean istree()
    {
       ArrayList<node<Ty>> Interior = new ArrayList<node<Ty>>();
       ArrayList<node<Ty>> Frontier = new ArrayList<node<Ty>>();
       Frontier.add(this);  // add root node to frontier
       /* Algorithm:
	  Select node N from frontier and move to interior.
	  Examine left,right childeren of N:  
             If one is already on frontier or interior list, 
               then this is not a tree
             else add childeren to Frontier.
	  loop until frontier is empty.
	*/
       boolean answer = true;  
       while (answer && Frontier.size()>0)
       {
          node<Ty> N = Frontier.remove(Frontier.size()-1); // take last node
          //node<Ty> N = Frontier.remove(0); // take first node
	  Interior.add(N); // add to interior
	  if (N.left!=null)
	    {
	      if (Interior.contains(N.left) || Frontier.contains(N.left)) 
		  answer=false;
	      else Frontier.add(N.left);
	    }
	  if (N.right!=null)
	    {
   	      if (Interior.contains(N.right) || Frontier.contains(N.right)) 
		  answer=false;
	      else Frontier.add(N.right);
	    }	  
       }// while
       return answer;
    }// istree

}//node