Questions related to recursion

Question

Questions related to recursion

Navigation

#1 by (4 votes)
#2 by (1 votes)

4

Good afternoon. I'm developing recursive methods that work on a binary search tree, but I'm having a hard time recursion.

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

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 those on the right side have a higher height it only continues to check the left side. My problem with recursion is that I do not know how I can make it go to both sides, right and left. For example, if I am in the root and it 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.

java

asked by anonymous 18.11.2015 / 22:38

2 answers

1

    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
    }

18.11.2015 / 23:10

Check if there is a Jquery internet connection Functions of cast or direct cast. What is the best option?

score 4 · Accepted Answer

You just call the recursive method twice. For the height of the tree will be one more 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 does not make much sense if you use an accumulator (this additional parameter cont you are using) since you can not use tail recursion unless you pass a "stack" "as an additional parameter (I can give you an example if you find it necessary).