15.5, LCA in a BST in java

#1

Is there a special reason why the answer to 15.5 is formatted with two nested while loops? it seems the outer loop will be broken as soon as you reach the LCA. I wrote my code with an if else statement within the while loop (with the same condition) as so:

public static Node lca(Node a, Node b, Node root) {
        // orient the nodes so that a is the lesser node and b is the greater node
        if (a.data > b.data) {
            Node tmp = a;
            a = b;
            b = tmp;
        }
        Node trav = root;
        while(trav.data < a.data || b.data > trav.data) {
            if (trav.data < a.data) {
                trav = trav.right;
            }
            else {
                        trav = trav.left;
            }
        }
        return trav;
    }

I’ve run it through a few test cases, and it seems to work, but I want to make sure the logic is solid. The loop works as the first part of the book solution (the if p.data < s.data) and the else condition
will move the node to its right child until the lca is reached, am i missing something?

0 Likes
#2

Hi @Rhuang97,

Thanks for your question, and there is no specific reasons to use two nested while loops. I think your implementation is correct. Our solution is more like a style when I solved this problem. Because when we are descending down in the searching for LCA, we want to keep going to one direction and then switch to another direction and keep going on another direction.

1 Like