For difficult recurenses like below, exist any trick to understand their result

[Leonidas Savvides]

For difficult recurenses like below, exist any trick to understand their result?

      // recursively determine the depth
   public int depth() 
   {
      return calculateLevel( root );
   } // end method depth

   // recursively determine the depth
   private int calculateLevel( TreeNode node )
   {
	  // if node is a leaf
      if ( node.rightNode == null && node.leftNode == null )
         return 0;
      else 
      {
         // search each of the subtrees
         int left = 0;
         int right = 0;

         if ( node.leftNode != null )
            left = calculateLevel( node.leftNode );

         if ( node.rightNode != null )
            right = calculateLevel( node.rightNode );

         // pass on the depth of the deeper subtree
         if ( left > right )
            return left + 1;
         else
            return right + 1;
      } // end else
   } // end method calculateLevel 

[Ireneusz Kordal]

Hi,

There is a logic error in this code.
A depth of null node should be 0, but a depth of not null node that has both descendants null should be 1.
The other problem is that if you pass null as argument to this function, it will throw NullPointerException.

Try this version:

      // recursively determine the depth
   public int depth() 
   {
      return calculateLevel( root );
   } // end method depth

   // recursively determine the depth
   private int calculateLevel( TreeNode node )
   {
       // null node has 0 depth
      if ( node == null )
         return 0;
      else 
      {
         // calculate depth of left subtree
         int left = calculateLevel( node.leftNode );

         // calculate depth of left subtree
         int right = calculateLevel( node.rightNode );

         // return greather depth of left & right
         // add 1 to it (as a depth of 'current' node
         if ( left > right )
            return left + 1;
         else
            return right + 1;
      } // end else
   } // end method calculateLevel 

I think there is no any magic trick - you must play a while with recursion, and you'll get in the end.
Look and play with examples of code for calculating a factorial (a classic recursion example), fibonaci, hanoi.

[Leonidas Savvides]

I did the simples fibonaci, hanoi. I just get confused easily...
please note that this is from
deitel java how to program 7/E, and works you may find code online or request to submit it me... calculate binary tree level depth
// Exercise 17.25 Solution: Tree2.java // Chapter 17 Data Structures
BTW what kinds of files may attached in forum?

[Leonidas Savvides]

// Exercise 17.19 Solution: Tree.java

correct exe number...above

[Jeanne Boyarsky]

Leonidas Savvides wrote:BTW what kinds of files may attached in forum?

Only images.

I think the way to look at recursion is to make sure you can find the recursive and base cases. Then look for how you get from one to another. Tracing the code often helps with that.