Doubts related to recursion

Question

Good afternoon. I am developing recursion methods that work on a binary tree of research, but I am having great difficulties in recursion.

For example, the method below should return the tree height:

public int altura(){
      return altura(root,0);
  }

  private int altura(Node n, int cont){
      if(n==null) return 0;
      cont += 1;
      if(n.left != null)
          return altura(n.left, cont);
      if(n.right != null)
          return altura(n.right, cont);
      return cont;
  }

however, it returns only the height of the nodes to the left side of the root, and when the right side has a higher height it continues only checking the left side. My problem with recursion is I don’t know how I make it go both ways, right and left. For example, if I am at the root and she has two children, I want the method to be applied both to the left and to the right, but in the method below it only applies to the left.

Answer 1

Just call the recursive method twice. For the height of the tree will be one plus the height of its largest subtree, so it is necessary to evaluate both sides before determining the height. An example would be:

  private int altura(Node n){
      if(n==null) return 0;
      int alturaE = altura(n.left);
      int alturaD = altura(n.right);
      if ( alturaE > alturaD )
          return alturaE + 1;
      else
          return alturaD + 1;
  }

This is a case where it doesn’t make much sense to use an accumulator (this additional parameter cont that you are using) since it is not possible to use tail recursion unless you pass a "stack" data structure as an additional parameter (I can give an example if you find it necessary).

Answer 2

    public int altura()
    {
        return altura(raiz, 0);
    }

    private int altura(No n, int cont)
    {
        // Imagine we have the tree below:
        /*
         *               R
         *              / \
         *             A   B
         *            / \      
         *           /   \  
         *          C     D
         *
         */

        // Now imagine a the situation in during the execution.
        // We've reached the C, coming from A. So:
        // 1. the execution of altura( nodeA, 1) will not
        //   make exit W; but will do exit Y.
        // 2. the next execution of altura( nodeC, 2) will
        //         do exit 1.
        //
        // Observe that, in step 1, after returning, we *will not*
        // continue the execution for altura( nodeA, 1) - it already
        // returned!
        //
        if( n == null )             // Exit W
            return 0;
        cont += 1;

        if( n.left != null )        // Exit X
            return altura(n.left, cont);

        if( n.right != null )       // Exit Y
            return altura(n.right, cont);

        return cont;                // Exit Z
    }