2
\$\begingroup\$

I was referred here from StackOverflow, so here is what I posted over there:

So, for an assignment, I have to construct a binary search tree, plus an assortment of related functions. I have them all working, but I'm looking for a way to optimize my way of finding in-order predecessors and successors. Here's my code for finding the predecessor (successor is, of course, nearly identical):

public double findPredecessor(double num) {
        if(this.has(num) == true) {
            node temp = this.root; 
            node iterator = this.root; 
            node returner = null; 

            while(temp.key != num) { //match the passed "num" to a key
                if(num < temp.key) {
                    temp = temp.left; 
                } else {
                    temp = temp.right; 
                }
            }

            if(temp.left != null) {
                return findMaxInternal(temp.left);  
            }

            while(iterator != null) {
                if(temp.key < iterator.key) {
                    iterator = iterator.left; 
                } 
                else if(temp.key > iterator.key) {
                    returner = iterator; 
                    iterator = iterator.right; 
                }
                else break; 
            }
            return returner.key; 
        }
        else return Double.NaN; 
    }

Yes, it is part of the assignment that my function take a double as argument, and not a node. I'm looking to see if there is a way that I can do this in one loop, to cut a bit on running time. I know that two successive, non-nested loops still is O(n), but still.

\$\endgroup\$
2
\$\begingroup\$

CodeReview is a good place for this question....

There are a few things that you should consider...

Style

node is a bad name for a Java class. Standards for Java are that Class names are CamelCase, and your node class should be called Node.

Using == to compare double values is often a cause of bugs. In this case I believe it is 'safe', but you should be aware that it is, in general, a 'bad idea'.

It is typical, though not required, that when you have an if {.....; return ...} block that you do not have an else block. For example, you have:

if (this.hasNum(...)) {
    .....
    return returner.key;
} else {
    return Double.NaN;
}

In this case the else block is not necessary, and it could simply be:

if (this.hasNum(...)) {
    .....
    return returner.key;
}
return Double.NaN;

Otherwise, the style is good.

Logic

You actually loop through the tree three times. I presume hasNum(...) also walks the tree.

With problems like this you can reduce the problem to a single walk of the Tree.

node match = null;
node current = root;
node predecessor = null;
// walk the tree until we find our exact match....
// Our predecessor node will follow us whenever we take a right branch....
while (current != null) {
    if (current.key == num) {
        match = current;
        break;
    }
    if (num < current.key) {
        current = current.left;
    } else {
        predecessor = current;
        current = current.right;
    }
}
if (match == null) {
    return Double.NaN;
}
if (match.left != null) {
    predecessor = match.left;
    while (predecessor.right != null) {
        predecessor = predecessor.right;
    }
}
if (predecessor == null) {
    return Double.NaN;
}
return predecessor.key;
\$\endgroup\$
  • \$\begingroup\$ In the future, please refrain from posting complete solutions to homework problems. \$\endgroup\$ – 200_success Nov 12 '13 at 18:46
  • \$\begingroup\$ perhaps.... but his solution was accurate.. just sub-optimal \$\endgroup\$ – rolfl Nov 12 '13 at 19:27
  • \$\begingroup\$ Yes, but it's also possible to guide the student towards a better solution without spelling out the entire code. Ending the review with a hint that a single-walk solution is possible would have sufficed. (It is, after all, an assignment, so the student should be able to figure it out.) \$\endgroup\$ – 200_success Nov 12 '13 at 19:33
1
\$\begingroup\$

@rolfl wrote a great review. I just have a few minor comments to add.

The original code had a bug: if the num parameter refers to the smallest item in the tree, then a NullPointerException would be thrown. @rolfl fixed that for you without saying so.

Your temp and iterator (or match and current, as @rolfl calls them) are redundant variables. Only one is needed.

If you are doing the hasNum() check, then the way to do it would be to return early.

if (!this.hasNum(num)) {
    return Double.NaN;
}
// The rest of the code here
...

That way, you save one level of indentation, and eliminate the suspense of having to wade through a short story before reaching the else finale. Anyway, it's a moot point, since you're better off not calling hasNum() at all.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.