Lowest Common Ancestor of a Binary Search Tree code was not accepted

Question

Q: Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

---

I tried to write two ways to solve the problem. The second one is accepted, but I don't understand why the first one is wrong.

Codes are as following:

1:

public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q) {
    int max = Math.max(p.val, q.val);
    int min = Math.min(p.val, q.val);
    while(max<root.val) {
        root=root.left;
    }    
    while (min>root.val) {
        root=root.right;
    }      
    return root;
}
}

2:

public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    int max = Math.max(p.val, q.val);
    int min = Math.min(p.val, q.val);
    while (max<root.val||min>root.val) {
         root=root.val<min?root.right:root.left;
    }      
    return root;
}
}

Is there any difference if I split the while loop? Thanks!

Answer 1

The reason is that the first attempt only goes right after it's done going left, which means any target node that goes right and then left can't be reached.

For example:

      3
 2         8
         6
        5 7
       4

In the above tree, the lowest common ancestor of 4 and 7 is 6, but it can't be reached.

Answer 2

Here is the modified code based on your first one

public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q) {
    int max = Math.max(p.val, q.val);
    int min = Math.min(p.val, q.val);
    while (max<root.val&&min>root.val) {
     root=root.val<min?root.right:root.left;
    }  
    while(max<root.val) {
        root=root.left;
    }    
    while (min>root.val) {
        root=root.right;
    }      
    return root;
}
}