/* Binary Trees   

We've seen how a linked list can be a very flexible data structure compared
to an array.  But there are also problems with lists, as revealed by the
"binary search" example - the elegant efficiency of that algorithm is totally
lost when using a linked list representation because of the need to follow
pointers.  One alternative is to use a *doubly linked list*, where a cell
has both a "tail" and a "previous" pointer.  Now if we keep both a pointer
to the front and end of the list, then certain operations can become more
efficient: e.g., adding an element to the end of the list becomes a 
constant time operation.  However, all of our other list operations (insert,
delete, etc) will now have to maintain this extra pointer appropriately.  It
still does not solve all the deficiencies of linked lists.

Trees, a fundamentally important data structure in computer science,
can be implemented in a similar manner as linked lists.  In fact, if
every cell has not just one "tail" but several "offspring" or child
nodes, then we have a much more complex structure that resembles an
upside-down tree, with the "root" at the top.  The root node (cell)
takes on the same role as the first cell as a linked list.  A tree
structure is even more naturally recursive than a linked list.  Most
operations on lists can be defined just as easily non-recursively as
recursively.  Not so with trees.  We will first look at "binary"
trees, where each tree node has two child nodes: a left and a right.
The "leafs" of the tree are nodes whose left and right pointers are
both null.  If all the right (or all the left) nodes of a tree are
null, then we would have the equivalent of a linked lists.  Thus trees
are a more *generic* data structure than lists.

Although we've seen how to write polymorphic data structures using the 
<A> construct, we'll keep it simple first and use nodes where the head
is just an integer.

*/

public class node
{

    public int head;
    public node left, right;

    public node(int h, node l, node r)
    { head=h; left=l; right =r; }
    public node(int h) // alternate constructor sets left,right to null
    { head=h; left=right=null;}

    // function to compute the number of nodes in a tree, recursive:
    public static int size(node T)
    { if (T==null) return 0; 
      else return 1 + size(T.left) + size(T.right);
    }

    // The difference between this functions and the "length" function
    // for lists is that here we REALLY benefited from recursion.  If you
    // don't believe me, try to write it without recursion.  In order
    // to visit all the nodes of a tree, we can't proceed in a linear
    // fashion.  We must *backtrack* to previous interior nodes we've
    // visited so that we can visit the other branch.  This is what
    // recursion does so well.  Furthermore, the time complexity of the
    // recursive function is still O(n), where n is the number of nodes in 
    // the tree, because every node is visited at most twice.

    // Because the function was recursive, it was easier to write it in
    // the static style (otherwise, you'd have to check if both the left
    // and right pointers are null).

    // Here's a function to determine if a number x is inside tree T:

    public static boolean member(int x, node T)
    {
      return (T!=null && (x==T.head || member(x,T.left) || member(x,T.right)));
    }

    // member function in the oop style also possible, note differences:
    public boolean memb(int x)
    {
	if (x==head) return true;
	return ( (left!=null && left.memb(x)) ||
		 (right!=null && right.memb(x)) );
    }

    // Here's a function to find the largest value in a tree, in the
    // oop style, but still recursive
    public int largest()
    {
	int ax = head;  // current largest.
	int ll, lr; // largest ints on subtrees
	if (left!=null) 
	    {
   	       ll = left.largest();
	       if (ll>ax) ax = ll;
	    }
	if (right!=null)
	    {  
		lr = right.largest();
		if (lr>ax) ax = lr;
	    }
	return ax;
    }//largest oop style

    // You do one: write a function that adds up all the numbers in a tree
    public static int sum(node T)
    {
	if (T==null) return 0;
	else return  T.head + sum(T.left) + sum(T.right);
    }


    // Printing a tree.  It is difficult and unnecessary to generate the
    // look of a tree in text.  However, it is possible to visit the tree
    // and print out every element.  Write a procedure that simply visit
    // each node and print the head of each node:

    public static void printtree(node T)
    {
	if (T==null) return; 
	printtree(T.left);
	System.out.print(T.head+" ");
	printtree(T.right);
    }


    /*** sample usage:
    public static void main(String[] args)
    {
	node T = new node(5,new node(4,null,new node(3)),
			  new node(2,new node(1),null));
	System.out.println(node.size(T));
	System.out.println(T.memb(3));
	node.printtree(T);
	System.out.println("\nlargest: "+T.largest());
    }
    ***/
/*
    Now you should ask the question: what's the big deal with trees,
    what advantage do they give us?  Well, if we only use trees as
    above, there really isn't much advantage, unless the nature of the
    data we're representing is naturally a tree (like a family tree).
    But the operations we've seen are still O(n) operations - just
    like with lists, plus recursion is often unavoidable.  To make
    better use of trees, we must consider trees of special forms.  On
    average, the length of any "branch" (path from root to a leaf) in
    the tree is log(n), because the number of nodes on each successive
    "level" of the tree is on average twice as many as the previous
    level.  If we can guarantee that the tree is "balanced", then it
    will be the case that even in the worst case, the length of a
    branch will be log n, a very small number even if n is in the
    billions and trillions (ever wonder how an Internet search engine
    can work so fast?).

    Unfortunately, balanced trees can be difficult to maintain.  Instead,
    we first look at a kind of tree called a "binary search tree".

    Gee, why do the words "binary search" sound familiar? :-)

    Binary search trees have the property that (recursively) for
    all nodes N, N.head >= all numbers on the N.left (not just the
    left node, the entire left subtree!) and N.head < all numbers
    on N.right.  Binary search trees can store any data for which 
    "<=" can be meaningfully defined (such as strings and alphabetical
    ordering).  Most operations on binary search trees only have to
    descend through one branch of the tree.  Since the average "height"
    of a branch is log n, this will allow us to take advantage of 
    the tree structure.  With such a tree, the "binary search" algorithm
    we saw on arrays can be recovered, with average time log n, since
    each time we look at a number, we elminate (on average) half the 
    choices.  Furthermore, recursion is not as essential as before, since
    we only need to worry about following one branch of the tree.

*/
    /***************** Binary Search Tree Routines ****************/

    // Check if a given tree is indeed a search tree
    // This procedure is still recursive because it still needs to
    // examine all parts of the tree.

    private static boolean issearchtree(node T, int min, int max)
    {
        if (T==null) return true;  // vacuously true
	if (T.head<=min || T.head>max) return false;
	return ( issearchtree(T.left,min,T.head) &&
		 issearchtree(T.right,T.head,max) );
    }

    public boolean isbst()
    { return issearchtree(this,0x80000000,0x7fffffff); }

    // The isbst public method invokes the private issearchtree method
    // by passing in the expected parameters.  Note there's no reason
    // why the interface procedure (isbst) can't be in the oop style while
    // the interior procedure is in the static style.

    // finding if something exists in a binary search tree, returning
    // the node that it found.  returns null if x is not in tree.
    // note that recursion is not needed, because we're always following
    // one of the left/right pointers, not both.
    public node intree(int x)
    {
	node i = this;
	while (i!=null && i.head!=x)
	    {
		if (x<i.head) i=i.left;
		else i=i.right;
	    }
	return i;
    }

    // inserting into a tree:
    public void insert(int x)
    {
	// need to find a node that has a null slot.
	node i = this;
	boolean done = false;
	while (!done)
	{
	    if (x<=i.head)
		{
		    if (i.left==null) 
			{ i.left = new node(x);
			  done = true;
			}
		    else i=i.left;
		} // go left
	    else 
		{
		    if (i.right==null)
			{
			    i.right = new node(x);
			    done = true;
			}
		    else i=i.right;
		}//go right
	}//while
    } //insert

    /* Deleting from a Binary Search Tree  - from 12/1 class

       To delete a node from a search tree, it is possible that the node
       to be deleted is an interior (non-leaf) node, in which case we
       need to replace it with another node in the tree.  Furthermore,
       we must do this in a way that preserves the binary SEARCH tree
       property.  The strategy is to replace the deleted node with 
       the largest node on its left subtree, or, if the left subtree
       is null, move up the right subtree.
       
       We also have to be careful that the node deleted is not the root node.
       The delete procedure therefore need to return a pointer to the
       possibly new root of the tree.
    */

// method to delete and return the smallest node in a non-null search tree. 
// The method takes a "previous" node parameter, which is null if the function
// is called on the root of a tree.  There is one special case that's not
// taken care of by this procedure: when there is only one node in a tree,
// it naturally is also the smallest.  In this case, the procedure does not
// know how to delete it.  That is, it would not know what the "previous"
// pointer is.  One solution to this is to use a "parent" pointer in every
// node, in addition to left and right.  But that would create its own
// nightmares as well.

    public node smallestnode()
    {
	node current = this;
	node previous = null;
	while (current.left!=null)
	    { 
		previous = current;
		current = current.left;
	    } 
	// at this point, current is pointing to node to be deleted.
	if (previous !=null) previous.left = current.right;
	return current;  // return deleted node
    }  // smallest


    node largestnode()
    {
	node current = this;
	node previous = null;
	while (current.right!=null)
	    {
		previous = current; 
		current = current.right;
	    }
	if (previous!=null)
  	   previous.right = current.left;
	return current;
    }//largest

    // delete x from tree, return root pointer
    public node delete(int x)
    {
	node current = this;
	node previous = null;
	int lrflag = 0; // 0 for left , 1 right;

	// find node to delete
	while (current!=null && current.head !=x)
	    {
		previous = current;
		if (x<current.head)
		    {
			current=current.left;
			lrflag = 0;
		    }
		else
		    {
			current=current.right;
			lrflag = 1;
		    }
	    }//while
	if (current==null) return this;
	node replacement = null;
	if (current.left !=null)
	    {
		replacement = current.left.largestnode();
		if (replacement==current.left)
		    current.left = null;
		// graft the replacement in place of current
		replacement.left = current.left;
		replacement.right = current.right;
		if (previous != null)
		    {
		      if (lrflag==0) previous.left=replacement;
		      else previous.right=replacement;
		    }
	    }
	else
	    {
		if (previous!=null)
		    {
			if (lrflag==0)
			    previous.left=current.right;
			else 
			    previous.right=current.right;
		    }
		replacement = current.right;
	    }
	if (this == current) return replacement;
	else return this;
    }//delete

}  // class node