What is wrong with this lowest common ancestor solution?


  • 1
    S
    //  Definition for a binary tree node.
       class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
      }
    
    public class Solution {
        public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null || p == null || q == null)
            {
                return root;
            }
            
            // if p and q are both to the left and right of the root then
            // root is the lca of p and q
            if(root.val > p.val && root.val < q.val)
            {
                return root;
            }
            else if (root.val > p.val && root.val > q.val) // both p & q are to the left of root
            {
                return lowestCommonAncestor(root.left, p, q);
            }
            else // both p & q are to the right of root
            {
                return lowestCommonAncestor(root.right, p, q);
            }
            
        }
        
        public static void main(String[] args)
        {
        	TreeNode root = new TreeNode(2);
        	root.left = new TreeNode(1);
        	TreeNode ancestor = lowestCommonAncestor(root, root.left, null);
        	System.out.println(ancestor.val);
        }
    }

  • 0

    You are assuming that p.val < q.val. This is not necessary. Also it is possible that either of p or q might be the LCA themselves.

    To resolve both issues, you can replace this if clause

    if(root.val > p.val && root.val < q.val)
        {
            return root;
        }
    

    with

    if(root.val >= Math.min(p.val, q.val) && root.val <= Math.max(p.val, q.val))
        {
            return root;
        }
    

    The minimum and maximum will ensure the test is correct and the equality will test out the cases when either of the input nodes is the LCA themselves.


Log in to reply
 

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