# In-order Predecessor BST review

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.

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;

• In the future, please refrain from posting complete solutions to homework problems. – 200_success Nov 12 '13 at 18:46
• perhaps.... but his solution was accurate.. just sub-optimal – rolfl Nov 12 '13 at 19:27
• 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.) – 200_success Nov 12 '13 at 19:33

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