CODEWITHSUNDEEP
java
LunchBuket
LunchBuket

Reputation: 1

I'm working on a binary search tree for my independent class and I can't figure out why this isn't returning the correct height

public int getHeight() {
    return heightFinder(root, 0);
}

This is the recursive method that actually figures out the height, it compares the count of one path to the count of another path and then should pick the higher count all the way up.

public int heightFinder(BTNode roo, int count) {
    if(roo == null) {
        return count--;
    }
    else
        return (heightFinder(roo.getLeft(), count++) > heightFinder(roo.getRight(), count++)) ?
                heightFinder(roo.getLeft(), count++) : heightFinder(roo.getRight(), count++);
}

Upvotes: 0

Views: 36

Answers (2)

Joop Eggen
Joop Eggen

Reputation: 109557

Either of these two variants are possible

/** Depth of current subtree. */
public int heightFinder(BTNode roo) {
    return roo == null
        ? 0
        : 1 + Math.max(heightFinder(roo.getLeft()), heightFinder(roo.getRight()));
}

You did pass a count:

/** 
 * Entire tree depth.
 * @param count length from root to current node.
 */
public int heightFinder(BTNode roo, int count) {
    return roo == null
        ? count
        : Math.max(heightFinder(roo.getLeft(), count + 1),
                   heightFinder(roo.getRight(), count + 1));
}

Doing count++ will have total different effects than count + 1 and that after the old value is used. It cannot be repeated for instance; would need to be stored in a countPlus1. Also you have 4 recursive calls, as you do not store the result of the recursive call.

Both variants have a different perspectives: the first says: what is the depth of left and right subtrees (without the depth of the node we are in), and the second keeps the depth till the current node.

As you need to compare the depths of left and right, so compare partial results, not based on any depth till the current node, the first solution is more elegant.

Of course, Math.max is phantastic here.

Upvotes: 2

Joachim Sauer
Joachim Sauer

Reputation: 308041

The problem is this code:

heightFinder(roo.getLeft(), count++) > heightFinder(roo.getRight(), count++)) ?
heightFinder(roo.getLeft(), count++) : heightFinder(roo.getRight(), count++)

For each heightFinder call you execute count++ which will increment count and return the new value.

Assuming that count starts out as 0 (as it does on the first invocation) you'll pass 1 to the first heightFinder call, 2 to the second heightFinder call and 3 to the third heightFinder call.

Additionally you should really remember the values for the first 2 calls instead of re-executing the "winning" branch. Because otherwise you'll traverse the whole tree multiple times for no real benefit, but that one doesn't affect correctness, only performance.

Upvotes: 3

Related Questions