(C) Samuel Marateck, 2004
Given the class

class Node
{  Object data ;
   Node left;
   Node right;
}

These are the steps you follow to write a recursive tree method.

1.Write the heading, e.g., public void test( Node t)

2 If a general traversal is needed in which all the nodes are visited,
type the if statement as if( t != null). In addition, if you want to
visit all the nodes except the leaves, type: if( ! isLeaf(t) ),
where

private boolean isLeaf( Node t)
{ return t.left == null && t.right == null;
}

You must make sure, however, when you use isLeaf the value of t is not null;
otherwise you will dereference the null pointer.  For instance, if your method
is traversing a tree that is not full, e.g.,

                  1
                 /  \
                2    3
               /  \ /
              4   5 6

and your method is:

private boolean inOrder( Node t)
{ 
    if( !isLeaf(t) )
    {
      inOrder(t.left);
      System.out.println(t);
      inOrder(t.right);
    }
}

when the execution backtracks from node 6 to node 3, executes
System.out.println(t), and then executes inOrder(t.right), the value of t.right
will be null. Then when isLeaf(t) is executed, t will be null and the Java
Virtual Machine will throw a nullPointerException.  So in general, you cannot
substitute if( ! isLeaf(t) ) for if( t != null).  

We now see why your method should be written as:

private void inOrder( Node t)
{
    if( t != null )
    {
      inOrder(t.left);
      System.out.println(t);
      inOrder(t.right);
    }
}


3. Depending on whether a preorder, inorder or postorder traversal, write
test(t.left), test(t.right) and place what should be done at the node either
before, in the middle, or after the recursive calls, respectively.

4. End the if statement.

5. If you want to test a value at a node and have that value passed
back to the calling program, write the heading as: 
public int test(Node t) and finish the method with a return.

6. If you write a recursive tree  that returns a value,
the left and right branching should be done in an assignment statement, e.g.,

height = 1 + max( height(t.left), height(t.right) )