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 &lt; temp.key) {
                    temp = temp.left; 
                } else {
                    temp = temp.right; 
                }
            }

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

            while(iterator != null) {
                if(temp.key &lt; iterator.key) {
                    iterator = iterator.left; 
                } 
                else if(temp.key &gt; 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 &lt; 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;