1

Im having trouble with a method that finds the height of the closest leaf. What i have just counts all of the leafs. would i have to separate the recursive calls into two conditional statements to check each one independently? any help or suggestions would be appreciated

this is my method

//find the distance to the closest leaf 
public int closeLeaf() 
{ 
    int distance;
    return distance = closeLeaf(root);
}

private int closeLeaf(StringNode n)
{
    int dist = 0;

    if(n == null)
    {
        dist = 0;//empty tree
    }
    else if(n.getLeft()== null && n.getRight()== null)
    {
        dist++;
    }

    else
    {

        dist =closeLeaf(n.getLeft()) + closeLeaf(n.getRight());



    }
    return dist;

}
alexthefourth
  • 127
  • 1
  • 11
  • 23

2 Answers2

3

Returning values

Please don't do this:

int distance;
return distance = closeLeaf(root);

Just:

return closeLeaf(root);

On to the real question

Here you're adding up the distance to each leaf:

dist = closeLeaf(n.getLeft()) + closeLeaf(n.getRight());

You probably just want to get the minimum of the two values (to tell you the distance to the closest one).

Brendan Long
  • 53,280
  • 21
  • 146
  • 188
1

Instead of

dist =closeLeaf(n.getLeft()) + closeLeaf(n.getRight());

which increments dist for every node encountered, use a static/class member variable that gets incremented each time the closeLeaf function is called.

Limit the recursion to finding a leaf, and the value of dist when you find one will give you the height of the closest leaf.

KK.
  • 783
  • 8
  • 20
  • would the variable go outside of the method? – alexthefourth Oct 27 '11 at 01:06
  • @alexthefourth. I would prefer it going outside of the method. But you can also use a static variable. Depends on your choice. – KK. Oct 27 '11 at 01:15
  • i havent seen that before, i havent seen alot since its my second java class. but can you give me a rough idea about hwo that would be implemented? would i have to add another method that would increment the variable each time closeLEaf is called? – alexthefourth Oct 27 '11 at 01:26
  • 1
    @alesthefourth. Have a look here. (http://download.oracle.com/javase/tutorial/java/javaOO/variables.html). In short, if you can, go through the Oracle java tutorial once. It will help you get the hang of things quickly. – KK. Oct 27 '11 at 01:34
  • @Brendan Long. Indeed it is. It wouldn't be wrong, but it sure will be ___bad___. Thanks for rectifying. – KK. Oct 27 '11 at 01:38
  • if its a bad way of doing it, is there a way of doing it inside the closeleaf method? – alexthefourth Oct 27 '11 at 01:51
  • @alesthefourth. Using member variables (fields) is not a bad thing, you will be using them ___a lot___. It is using _static_ which is bad. – KK. Oct 27 '11 at 01:54
  • @alexthefourth. Here's why static variables should be rarely used. http://stackoverflow.com/questions/1766715/when-not-to-use-the-static-keyword-in-java – KK. Oct 27 '11 at 02:01