My Java Solution


  • 91
    J
    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root.val > p.val && root.val > q.val){
                return lowestCommonAncestor(root.left, p, q);
            }else if(root.val < p.val && root.val < q.val){
                return lowestCommonAncestor(root.right, p, q);
            }else{
                return root;
            }
        }
    }

  • 47
    F

    A non-recursive version.

    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            while (true) {
                if (root.val > p.val && root.val > q.val)
                    root = root.left;
                else if (root.val < p.val && root.val < q.val)
                    root = root.right;
                else
                    return root;
            }
        }
    }

  • 2
    D

    I guess the worst case running time is O(n). Right?


  • 1
    F

    Yes, for example, if most nodes in the tree only have one child (left child or right child) and node p and node q are in low position of the tree, then the program will not terminate until we find the correct node (by that time, we probably have nearly traversed the whole tree.)


  • 0
    H

    got it.............


  • 0
    D

    What if one of the target is not found in the BST? In which case, shouldn't the program return null?


  • 0
    A

    @fanofxiaofeng This is such an amazing solution :)


  • 1

    I think a BST may contain the same keys.
    So in some cases that are not among test cases of this problem, this solution will give a wrong answer.


  • 3
    O

    @fallcreek said in My Java Solution:

    I think a BST may contain the same keys.
    So in some cases that are not among test cases of this problem, this solution will give a wrong answer.

    Agree with @fallcreek , in this case

    6 (root)
      \
       6 (p)
         \
           6 (q)
    
    

    Your program will return root instead of correct answer.

    After all, this is a nice answer in case the problem specifically states every element in the BST are distinct.

    Below is my code considering identical elements situation:

    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            TreeNode[] ans = new TreeNode[1];
            lca(Integer.MIN_VALUE, Integer.MAX_VALUE, root, p, q, ans);
            return ans[0];
        }
        
        private int lca(int bot, int top, TreeNode r, TreeNode p, TreeNode q, TreeNode[] ans) {
            if (r == null) return 0;
            if ((p.val > top || p.val < bot) && (q.val > top || q.val < bot)) return 0;
            int n1 = lca(bot, r.val, r.left, p, q, ans), n2 = lca(r.val, top, r.right, p, q, ans);
            if (n1 > 1 || n2 > 1) return 2;
            int n = n1 + n2 + ((r == p || r == q) ? 1 : 0);
            if (n > 1) ans[0] = r;
            return n;
        }
    }
    

  • 1
    A

    @ofLucas Please help me understand this basic concept. Can a binary search tree have duplicate nodes? I was under the assumption that left will always be lower than the root and right will always be greater than the root. Please advise.


  • 1
    M

    @jingzhetian

    The code is concise. However, what about the edge case: p or q is not in the tree? The problem does not define how to deal with the invalid input cases well.


  • 0
    D

    I have the same idea with this!


  • 0
    F

    Hi why is the non-recursive version different from the following:

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

  • 1
    R

    @FanChen

    NOTE: I WILL SWAP THESE 2 LINES TO JUST USE THE EXAMPLE PROVIDED

           while (root.val > p.val && root.val > q.val) root = root.left;
           while (root.val < p.val && root.val < q.val) root = root.right;
    

    After Swapping

           while (root.val < p.val && root.val < q.val) root = root.right;
           while (root.val > p.val && root.val > q.val) root = root.left;
    

    What is happening is that you need to repeat these 2 till the time you don't find the actual solution.

            _______6______
           /              \
        ___2__          ___8__
       /      \        /      \
       0      _4       7       9
             /  \
             3   5
    

    6 is the root and let's say you need to find the LCA of 3 and 5
    Now 6 > 3 and 6 > 5.... therefore 6 remains 6 (first while loop ends)

    1. Now the second condition is to check if 6 > 3 and 6 > 5 (2nd while) we see that this is satisfied. 6 => 2
      So it will give 2 as the answer --- > but the real answer is 4

    OK, so what happened? Your code is good but will fail for some test cases because logically swapping the 2 while statements should have given the correct solution in the first place. Which you see here it does not.

    So what I tried is

    while(true) {

    if(root.val >= p.val && root.val <= q.val) break;
    while 1
    while 2
    }

    but this gives another error -> there is no guarantee that p < q
    So, would recommend you to use the solution provided already. It's clean.

    But I hope you realized why the 2 while logic in not working :)


  • 0
    L
    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            int min=Math.min(p.val,q.val);
            int max=p.val+q.val-min;
            while(!(root.val>=min&&root.val<=max)){
                if(root.val>max) root=root.left;
                if(root.val<min) root=root.right;
            }
            return root;
        }
    }```

  • 0
    T

    @majun8cn I think that in the problem it says "....of two given nodes IN THE BST", and this means both p and q are in the tree for sure. So they didn't build any testcases with the invaild input you mentioned.


  • 0
    G

    @ofLucas Thank u so much for your code! I had the same doubt about duplicates and the same idea using markings to indicate what we have found so far. Below is your code, and I just add some explanations:

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            TreeNode[] ans = new TreeNode[1];
            /* the author used ans[0] cuz java do not support pass by reference;
             * could we use TreeNode ans = null? No! Even though when it comes to objects, 
             * java uses pass by value of the (pointers to the memory address), we could not change 
             * the "content" in the memory address using ans = r in the recursive functions, 
             * since ans is just a "copy"(pass by value) of a pointer to ans, and we only change 
             * that copied pointer to r, the ans in the original function has not been changed!
             * notice that if p or q is not in the BST, ans could be null;
             * */
            lca(Integer.MIN_VALUE, Integer.MAX_VALUE, root, p, q, ans);
            return ans[0];
        }
        
        private int lca(int bot, int top, TreeNode r, TreeNode p, TreeNode q, TreeNode[] ans) {
        	//is p or q possibly there?
            if (r == null) return 0;
            if ((p.val > top || p.val < bot) && (q.val > top || q.val < bot)) return 0;
            //this is the same idea as mine, to use n to mark 
            //whether we've found: (p or q) n=1; or (p and q) n=2;
            int found1 = lca(bot, r.val, r.left, p, q, ans), found2 = lca(r.val, top, r.right, p, q, ans);
            if (found1 > 1 || found2 > 1) return 2;//we do not rewrite ans[0] cuz n>2 indicates that we have already found them! 
            int found = found1 + found2 + ((r == p || r == q) ? 1 : 0);
            if (found > 1) ans[0] = r;
            return found;
        }

  • -1
    N

    @fanofxiaofeng I don't understand why "while(true)" works but "while(root != null) doesn't work. can you please explain this?


  • 0
    G

    @jingzhetian yes,good solution,you plenty use the features of BST,thx :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.