CODEWITHSUNDEEP
javatree
alexthefourth
alexthefourth

Reputation: 137

java binary search tree find closest leaf

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;

}

Upvotes: 1

Views: 1312

Answers (2)

KK.
KK.

Reputation: 783

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.

Upvotes: 1

Brendan Long
Brendan Long

Reputation: 54242

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).

Upvotes: 3

Related Questions