CODEWITHSUNDEEP
java
user5708826
user5708826

Reputation:

Lowest Common Ancestor recursively in Java

I've found a solution to the lowest common ancestor problem in java in leetcode. The problem stated otherwise is, find the lowest common ancestor of p and q with the BST rooted at root. Here's my code.

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);
        return left != null && right != null ? root : left == null?right :left;

    }

While this works for most cases, if the tree is something like this and the question is lowestCommonAncestor(1, 2, 3) or lowest common ancestor of 2 and 3 where root == 1;

1 -> 2 -> 3

Then to my mind the answer this solution will provide is 2, This is because after the recursion

left = null
right = 2

while the actual answer is 1.

However this solution works. Can someone help me understand what am I getting wrong here.

Upvotes: 0

Views: 198

Answers (2)

Tangoo
Tangoo

Reputation: 1449

After execution of TreeNode right = lowestCommonAncestor(root.right, p, q);,

you get:

left=null;
right=2;

At last, the result=(left!=null && right!=null)?root:(left==null?right:left);

Return result:2

Upvotes: 1

Andreas
Andreas

Reputation: 159106

Follow the logic:

lowestCommonAncestor(root=1, p=2, q=3):
    if (root == null || root == p || root == q) return root;
    //     false           false        false

    left = lowestCommonAncestor(2, 2, 3):
               if (root == null || root == p || root == q) return root
               //     false            true                return 2

    right = lowestCommonAncestor(null, 2, 3):
                if (root == null || root == p || root == q) return root;
                //      true                                return null

    return left != null && right != null ? root : left == null ? right : left;
    //         true        false                     false             : 2

Result: 2

Easiest way to follow the code is to use a debugger.

Upvotes: 1

Related Questions