My Java Solution which is easy to understand


  • 115
    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null || root == p || root == q)  return root;
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if(left != null && right != null)   return root;
            return left != null ? left : right;
        }
    }

  • 3
    W

    Thanks for sharing! How did you come up with this solution?


  • -18
    This post is deleted!

  • 1
    J

    The question said that "given two nodes in the tree"


  • 20
    P

    Yet another easy to read :

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if( root == p || root == q || root == null)
                return root;
            TreeNode left = lowestCommonAncestor( root.left,  p,  q);
            TreeNode right = lowestCommonAncestor( root.right,  p,  q);
            if(left == null)
                return right;
            else if (right == null)
                return left;
            else
                return root;
            
        }
    

  • 2
    P

    This solution doesn't work if there are duplicate nodes.

    [37,-34,-48,null,-100,-100,48,null,null,null,null,-54,null,-71,-22,null,null,null,8]
    node with value -100
    node with value -71

    Output: 37
    Expected: -48


  • 3
    P

    @pritamkarmakar If you have duplicate nodes then you can't say which one are you referring to in the question. So, dupicate nodes don't make sense in your test case.


  • 1
    P

    @piyush121 agree with you, I came up with the same solution but leetcode gave me this test case where my code failed.


  • 1
    P

    @pritamkarmakar I ran the same code. It got accepted for me. Can you paste your code snippet here ?


  • 1
    P

    @piyush121 sorry for the late reply. Here is my solution

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root == null || p ==null || q == null) return null;
        if(root.val == p.val || root.val == q.val)
          return root;
          
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        if(left != null && right != null)
          return root;
        
        return left != null ? left : right;
    }
    

  • 11
    P

    @pritamkarmakar Ok, so your problem is that you are comparing the values in the nodes. You should compare the node itself because the problem says you need to find the LCA of two TreeNodes not two values. I hope you get it.

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null || p ==null || q == null) 
                return null;
    
        if(root == p || root == q) // Made this change here in your code.
          return root;
          
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        if(left != null && right != null)
          return root;
        
        return left != null ? left : right;
            
        }
    

  • 8
    V

    I feel these solutions will go wrong if either node p or node q is not found in the tree.

    Because here, once a node is found and if the other one is not found, it assumes that the one that is found is the parent which is not necessarily true. It assumes it here,

    return left != null ? left : right;

    If I call lowestCommonAncestor() making 2 different instances of trees, both's nodes will be of type TreeNode, but they won't belong to the same tree.


  • 2
    I

    @vivek_23

    the question says this " (LCA) of two given nodes in the tree." so, your scenario is not valid for this question.

    Not saying this is a good or bad way to phrase this question, but i got bit by the same thought and when i discovered that the testcases didn't have the negative test because the question is phrased as above.

    My only take away was to read the question more carefully, that said, this was too subtle.


  • 0
    H

    Yet another trivial solution similar to Bitmap, if we want to know clearly what happened in each step. For me it's much easier to write and to read. And also easy to extend to 5 or even more nodes.

    public class Solution {
        private TreeNode lowestCommonAncestor = null;
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || p == null || q == null) { return null; }
            lowestCommonAncestor = null;
            recur(root,p,q);
            return lowestCommonAncestor;
        }
        /**
         * Using BITMAP
         *  1. nothing found in tree:           00 -> 0
         *  2. p found in tree:                 01 -> 1
         *  3. q found in tree:                 10 -> 2
         *  4. both p & q are found in tree:    11 -> 3
         */
        public int recur(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) { return 0; }
            int left = recur(root.left,p,q);
            if (left == 3) { return left; } // LCA found in left sub tree
            int right = recur(root.right,p,q);
            if (right == 3) { return right; } // LCA found in right sub tree
            int sub = left | right;
            if (sub == 3) { lowestCommonAncestor = root; return sub; }
            int curr = 0;
            if (root == p) { curr |= 1; }
            if (root == q) { curr |= 2; }
            curr |= sub;
            if (curr == 3) { lowestCommonAncestor = root; }
            return curr;
        }
    }

  • 0
    A

    You always walk the entire tree. Try pruning.


  • 0
    A

    @yuhangjiang Thanks for sharing, but this solution even after finding both the nodes go and traverse entire tree to look for a two nodes that are already being found. Is that something we can avoid?


  • 0
    K

    @yuhangjiang Can you tell me why we can't use if (root == null || root.val == p.val || root.val == q.val) in the first condition, thanks


Log in to reply
 

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