Binary Search Tree : Lowest Common Ancestor

this was my approach but it is failing testcase 2 and i don't know why. checking my 'output' for 5 hackos it reads 'CORRECT' so i don't know what's going on

This will not pass the case where v1 is an ancestor of v2.

Perfect solution! (y) :-)

couldn't think of a more perfect solution than this one.

I did it the same way, with a minor performance improvement: I arrange v1 and v2 so that I know which is larger:

node* lca_(node* root, int a, int b)
{
    if (b < root->data) {
        return lca_(root->left, a, b);
    }
    else if (a > root->data) {
        return lca_(root->right, a, b);
    }
    return root;
}

node* lca(node* root, int a, int b)
{
    if (a < b) {
        return lca_(root, a, b);
    }
    return lca_(root, b, a);
}

man, at first sight I thought this would be more like a medium question... but after thinking it through... meh

Thanks, that was really helpful. This is my C++ Solution

node * lca(node * root, int v1,int v2)
{
    node *cur{root};
    for (; cur->data > v1 && cur->data > v2; cur = cur->left);
    for (; cur->data > v1 && cur->data > v2; cur = cur->right);
    return cur;    
}

for example, for a tree: 4 2 3 1 7 6 8

if you want to find the lowest common ancestor of 6 and 8, your code outputs 7, but the correct answer should be 4!

I like simplicity of your solution. My brain finally has started to figure out (picking up) a pattern in recursion. But the only problem that I am facing as of now is I overcomplicated solution. Such as the one below.

if((root->data < v2 && root->data > v1)||(root->data > v2&&     root->data < v1)){
    return root;
}else if(root->data > v1&&root->data > v2){
    return lca(root->left,v1,v2);
}else if(root->data < v1&&root->data < v2){
    return lca(root->right,v1,v2);
}else{
    return root;
}

I think that in the first part of the code (// smaller than both) is useless because if both v1 and v2 are greater than root.data so the LCA is the root itself because all nodes on the right of the root are greater than it so the conditions inside the function will be only :-

//Bigger than both
if(root.data > v1 && root.data > v2){
    return lca(root.left,v1,v2);
}
//Else solution already found
return root;

I submited this code and it passed all test cases ...

This also works.

node * lca(node * root, int v1, int v2) {
    if (root == NULL || root->data == v1 || root->data == v2)
        return root;
    node * left = lca(root->left, v1, v2);
    node * right = lca(root->right, v1, v2);
    if (left != NULL && right != NULL)
        return root;
    if (left != NULL)
        return left;
    return right;
}

My approach is very similar but I am getting error in TestCase 2.I have been trying to figure that out for an hour but couldn't.What's so special about case 2?

consider this case: Tree size 3 and its contents are 4,2,1 and search for 2 and 1. As per correct solution provided, the output is returning as 2 but it should be 4 right?

this solution doesnot work with case 2 because you have not made a condition on root that if it is not null then check that v1 and v2 are greater or less.

What about some edge cases? 1) What if v1 == v2? 2) What if v1 is an ancestor for v2? Would your solution work then?

Hmm I never thought to use a value test. I used a recursive inTree() function to test if a value was in a particular subtree. The running times of all test cases was 0 so the recursion didn't hurt in this case.

https://www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor/submissions/code/25912799

bool inTree(node *head, int value) {
    if (head == NULL) {
        return false;
    } else if (value == head->data) {
        return true;
    } else {
        return inTree(head->left, value) || inTree(head->right, value);
    }
}

node * lca(node * root, int v1,int v2)
{
    if (inTree(root->left, v1) && inTree(root->left, v2)) {
        return lca(root->left, v1, v2);
    } else if (inTree(root->right, v1) && inTree(root->right, v2)) {
        return lca(root->right, v1, v2);
    } else {
        return root;
    }
}

pls help! i can't trace the code especially when it states (4<1 &&4 <7) or (4>1&&4>7). how the recursive calls r taking place..

pls help! i can't trace the code especially when it states (4<1 &&4 <7) or (4>1&&4>7). how the recursive calls r taking place..

My solution was so convoluted.

vector pathTo(node* root,int key){
  vector path;
  node* current = root;

  while (current != NULL && current->data != key) {
    path.push_back(current);
    if      (key data) current = current->left;
    else if (key > current->data) current = current->right;

  }
  if (current)
    path.push_back(current);
  return path;
}

node*lca(node*root,int x,int y){
  vector pathX = pathTo(root, x),
                pathY = pathTo(root, y);

  unordered_set s;
  int i;
  for (i = pathX.size()-1; i >= 0; --i)
    s.insert(pathX[i]);
  for (i = pathY.size()-1; i >= 0; --i) {
    if (!s.insert(pathY[i]).second) break;
  }
  return pathY[i];
}

I think in this counter example it wouldnt work:

v1 is 1 and v2 is 7

    4       
  /   \
2       6
 \     /  \
  3   5    7    
     /
    1

Answer we would get is 4 and the correct answer is 6.

Nice job. You can alternatively try to solve it iteratively like this to achieve O(1) space complexity since recursion takes O(log n) space.

HackerRank solutions.

It is better to first check if you have already found the lce and then decide which path to go.

To, the same idea without brackets would be like this:

node * lca(node * root, int v1,int v2)
{
   int diff1 = root->data - v1, diff2 = root->data - v2;
   if (diff1 * diff2 <= 0) return root;
   if (diff1 < 0) return lca(root->right, v1, v2);
   return lca(root->left, v1, v2);
}

I don't think it is a correct solution.. It will always return the root of tree after final evaluation.. All test cases except test case 2 are working becuase fro all of them root of the tree is the LCA..

Node lca(Node root,int v1,int v2){
    return root;     
 }

Try this, you will know what I am trying to say.. If you run the above code it will also fail only test case 2..

After we get the required node, in the shrinking phase of recursions we need a way so that we can contain the deepest recursive node in root and not the actual root of tree.. though I am not sure how to do that..

I think there's a bug in your code. Your code doesn't address the condition when v1 or v2 = root, in that case, the lca is the parent of the current root but your code will return current root and that's why it may be failing some test cases. Let's say, for this bst,

    40
   /
  20    <-- v1
 /                  lca = 40
10      <-- v2

if we are given v1 = 20, v2 = 10 then if we go through your code it'll return 20 as the lca but actually 40 will be the lca.

Have a look at my code. It passes all the test cases.

node * lca(node * root, int v1,int v2)
{
    if(v1<root->data && v2<root->data)
        if(node *tmp = lca(root->left, v1, v2))
            return tmp;
    if(v1>root->data && v2>root->data)
        if(node *tmp = lca(root->right, v1, v2))
            return tmp;
    return root;
}

this doesn't work for all the test cases.

Can someone explain this recursive solution to me? I'm not able to get the correct return value.

Beautiful!

The example input given to the problem in the description has Node 5 on left of Root node 1.

Which I do think will fail your solution.

static Node lca(Node root,int v1,int v2)
    {
        Node curr = root;
        
        while ((curr.data < v1 && curr.data < v2) || (curr.data > v1 && curr.data > v2)) {
            if(curr.data < v1 && curr.data < v2){
                curr = curr.right;
            }
            else {
                curr = curr.left;
            }
        }
        
        return curr;
    }

Changed it to iterative so the space complexity is O(1)

Here's my code:

def lca(root, a, b):
  node = root
  while node:
    if max(a, b) < node.data:
      node = node.left
    elif min(a, b) > node.data:
      node = node.right
    else:
      break
  return node

Does that help you?

I totally agree with you. It's a very unaccurate problem description.

Agreed. This one definitely needed better examples. Since we can't really ask for clarifications on the problems or can't see the test cases until after writing and executing our program, edge cases and clear definitions are paramount...

Yes. I knew what the LCA problem was already, but this question is really ment for people who aren't familiar with it yet, so they should have it spelled out. I was annoyed that the problem says nothing about how to handle duplicate values - if you have a tree full of 5's, do you put all the 5's on the left, all of them on the right, or balance it out somehow? I just assumed they didn't include such things in the tests and my code worked, but this should have been mentioned in the problem.

I agree. I was able to pass the test cases even though I had test ran it with an incorrect solution.

Only problem in #2 test case, Can you help me ..

static Node lca(Node root,int v1,int v2){ if(root==null){ return null; } if(root.data>v1 && root.data>v2) lca(root.left,v1,v2); if(root.data

same here.so do you know now what's the problem?

Yup, looks like HackerRank needs to do some QA on their questions.

I'd imagine a node cannot be considered its own ancestor. So I would think that you would need to return the parent of A.

A, which I think is wrong but seems to be what the problem is looking for.

You will have to return node A, because for the Lowest common ancestor problem, every node is considered a descendant of itself.

So if A is an ancestor of B, your lowest common ancestor would have to be A. Hope this clarifies your question.

return A