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)

why do you have return lca(root.right, v1,v2) as opposed to lca(root.right,v1,v2)?

BUT! The first example is not following your presumption (3 is not between 4 and 5). If it's just a mistake then it's confusing.

Brilliant solution!

I don't think this is going to work because consider a tree with 3 as the root node and has 4 as a left child and 5 as a left child. 5 has a right child 6. The least common ancestor for 4 and 6 would be 3, but according to your logic, it would be 5, which is incorrect. Value of common ancestor need not be between the two values. Look at the first example case of the problem

You should also have written, that you're doing a binary search for both values.

has to consider the scenario when v1 or v2 equal to root.data

here another java solution, but this solution destroys the tree lol

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

        return root; 
    }

Why are you smarter than me?

C++ solution :

Node *lca(Node *root, int v1,int v2) {
		// Write your code here.
        while((v1>root->data && v2>root->data) || (v1<root->data && v2<root->data))
        {
            if (v1>root->data) root=root->right;
            else root=root->left;
        }
        return root;
    }

Easiest solution https://www.youtube.com/watch?v=N9yepbXdOkI

Straight to the point. Cool, thanks for sharing this thought.

never had experience with tree, so maybe a stupid question: how do you get "The value of a common ancestor has to always be between the two values in question."? at least the first picture shows that "3" is the common ancestor of "4" and "5".

Good post but I was wondering if you could write a litte more on this subject? I’d be very thankful if you could elaborate a little bit further. Appreciate it..! https://www.pikdo.online/

O(height) python solution:

def lca(root, v1, v2):
    while(root != None):
        if(v1 > root.info and v2 > root.info):
            root = root.right
        elif(v1 < root.info and v2 < root.info):
            root = root.left
        else:
            break
    return root

This solution is false and will barely pass any test due to runtime errors and wrong answers. I don't know why it has this many upvotes while beeing crappy

I thought so too at fisrt, but this would not suit the first example they provide, where the lca of 4 and 6 is 3.

Had a similar thing with C but I'm getting seg faults. Any ideas? It works for half the test cases;

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

yes is exactly what I tought, the structure of the tree is already tell us how to proceed

that's very brilliant.

but i tried tracing the path from root to key1 and taken this path into a queue. did the same for key2 and returned the last common integer among the two queues.

complex right?

Thank you very, very much, RubenzZzZ!

My iterative approach

public static Node lca(Node root, int v1, int v2) {
        if (root == null)
            return null;
        Set<Node> set = new HashSet<>();
        set.add(root);
        Node node = root;
        while (node.data != v1) {
            node = v1 < node.data ? node.left : node.right;
            set.add(node);
        }
        set.add(node);
        Node n = root;
        node = root;
        while (set.contains(node)) {
            n = node;
            node = v2 < node.data ? node.left : node.right;
        }
        return n;
    }

just amazing

dang, didnt think of it! thank you so much!

good it helped me alot

I did the samething but getting a runtime error anytime there v1 or v2 eaqual root.info. Can anyone tell why? Posting my code above

I did the same thing but am running into errors then v1 or v2 are eaqual to node.info. Dont understand why

My Amazon interview experience https://freezefrancis.medium.com/amazon-sde-interview-experience-on-campus-e8444ee791b

Variant of this came in my interview: https://freezefrancis.medium.com/agoda-interview-experience-de6abc2c7347

This code does not pass all test cases

The solution is well thought, but I believe the following (custom) test case provides incorrect answer-

6

2 1 3 4 5 6

3 4

Expected - 1 Recieved - 3

The tree is same as the first example. Kindly let me know if I am misunderstanding something.

Respect!