CSC 17 Lab 9 : Tree Hugging

  			   Due Thursday 4/10


Download the programs node.java and treegraph.java.  treegraph.java
allows you to display a binary tree graphically.  see testnode.java
for example.  Please note that treegraph assumes the presence (in the
same directory) of a class "node" with public elements "head", "left"
and "right".

0. Start a main method that generates a random binary search tree with
   at least 10 elements. Use treegraph to display it.  For each of the
   problems below, write code in main to test it.  You probably want to
   put this in a separate class and file.


Add the following methods to the node class, after carefully studying the
sample programs I've provided.  Clearly mark where your code begins.
Note that some of these methods are for general trees, while others are
for binary search trees.


1. Write a method that prints the elements of a tree using a post-order
   traversal.


2. Write a method 

     public int count(Ty x)

   That returns the number of occurrences of the element x in a GENERAL tree.
   (as opposed to simple search, which just determines if there is one
    instance).


	What is the time complexity class of this method?  Answer this
	questions in comments inside your code.


3. write a version of the above function for binary search trees.  Do NOT
   use recursion.

	What is the time complexity class of this method?  


4. Write a method to return the smallest element of a binary search tree.
   NOW THINK! Where would that be?

     	What is the time complexity class of this method?


5. The "insert" method (for binary search trees) that I gave you used
   a while loop.  Write a version that uses recursion.  Hint: study the
   examples for "bsearch."

-------------------

6. Lab 9b (Thursday 4/10) Addition.

We've seen how to define the "depth" or "height" of a tree.  One may
also wish to know its "width".  That is, what is the node farthest to
the root from the left and the node farthest to the right.  We can
define the horizontal distance of a node to the root as follows: Each
node in a tree is reachable from the root by following a sequence of
left/right links.  Each time we go left, we decrease the horizontal
distance by one, and each time we go right we increase it by one.  The
root node has distance zero.  So nodes to the left of the root will
have a negative horizontal distance and those to the right will have
positive ones.  The width of the tree can then be defined as the
absolute value of the difference between the largest and smallest
horizontal distances.

Consider the following example:

	    6
          /   \
         5     2
          \
           7
            \
             8
              \
               9
	        \
                 10

The horizontal distance of the node containing 10 is +3, because we go
once left and four times right to reach it.  The width of this tree
is |-1 - 3| = 4.


Write a function inside the node class that returns the width of a tree.
That is, A.width() should return the width of A.