Code for finding Lowest Common Ancestor is not working for some test cases

Question

I am working on this exercise from Hackerrank(https://www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor/copy-from/158548633) In this exercise, we are given a pointer to the root of the binary search tree and two values v1 and v2. We need to return the lowest common ancestor (LCA) of v1 and v2 in the binary search tree. we have to complete the function lca. It should return a pointer to the lowest common ancestor node of the two values given.

lca has the following parameters:

• root: a pointer to the root node of a binary search tree

• v1: a node.data value

• v2: a node.data value

I know the recursive solution is easier but I tried this approach and couldn't find any reason for failing test cases. The below-mentioned solution passes only 6/10 test cases. I can't see all the 4 failed test cases but I can mention 1 test case.

here's my code

/*The tree node has data, left child and right child 
class Node {
    int data;
    Node* left;
    Node* right;
};

*/

vector<Node*> find(int v, Node* root)

{
    vector<Node*> ar;
    if (v == root->data) {

        ar.push_back(root);
        return ar;
    }

    if (v > root->data) {
        ar.push_back(root);
        find(v, root->right);
    }

    if (v < root->data) {
        ar.push_back(root);
        find(v, root->left);
    }
    ar.push_back(root);
    return ar;
}

Node* lca(Node* root, int v1, int v2)
{

    //this vector contains the nodes in path
    //to reach from root to node
    vector<Node *> a, b;

    //find function return the vector
    a = find(v1, root);
    b = find(v2, root);

    //index of the LCA in the vector
    int res = 0;

    //traversing the two vectors from
   //beg to end if two nodes are same
  //update the value of res. Final updated
 //value will give us LCA
    int n = b.size();
    if (a.size() < b.size())
        n = a.size();
    int i = 0;
    while (i < n) {
        if (a[i] == b[i])
            res = i;

        i++;
    }
    return a[res];
}

failed test case:

8

8 4 9 1 2 3 6 5

1 2

Expected output:

1

My output:

8

needed help to debug the code and to find the loophole in this approach.

Answer 1

Below pseudo code can be used for generating the code for LCA problem.

///////////////////

Recursively call on LCA function, one for left subtree and one for right subtree. If the the node is null then return simply null, else

If the value of node is equal to any of the value v1, v2 then simply return this node,

else call recursively for the subtrees.

Now when you receive the result for your 2 recursive calls, check ->

if both are null, then return null

if one is null and the other one is not null, then return the non-null node,

if both are not null, then return the root note itself.

Answer 2

your algorithm cannot work

• in find the vector produced by the recursive calls are lost so it like you do not do these calls, at the end you just get the vector produced by the initial call
• in lca even supposing find does the right thing you suppose the answer it at the same rank in the 2 vectors, why ?

A way to do is :

Node * Node::lca(int v1, int v2) {
  if ((data == v1) || (data == v2))
    return this;

  Node * r = (right == NULL) ? NULL : right->lca(v1, v2);
  Node * l = (left == NULL) ? NULL : left->lca(v1, v2);

  return ((r != NULL) && (l != NULL))
    ? this
    : ((r == NULL) ? l : r);
}

---

A full example :

#include <iostream>
#include <vector>
#include <iomanip>

class Node {
  private:
    int data;
    Node* left;
    Node* right;

  public:
    Node(int d) : data(d), left(NULL), right(NULL) {}
    void insert(int d);
    void draw(int level = 1) const;
    Node * lca(int v1, int v2);
};

void Node::insert(int d) {
  Node * n = new Node(d);
  Node * t = this;

  for (;;) {
    if (d > t->data) {
      if (t->right == NULL) {
        t->right = n;
        return;
      }
      t = t->right;
    }
    else if (t->left == NULL) {
      t->left = n;
      return;
    }
    else
      t = t->left;
  }
}

void Node::draw(int level) const {
  if (right != NULL)
    right->draw(level + 1);
  else
    std::cout << std::setw(level + 1) << '/' << std::endl;

  std::cout << std::setw(level) << data << std::endl;

  if (left != NULL)
    left->draw(level + 1);
  else
    std::cout << std::setw(level + 1) << '\\' << std::endl;
}

Node * Node::lca(int v1, int v2) {
  if ((data == v1) || (data == v2))
    return this;

  Node * r = (right == NULL) ? NULL : right->lca(v1, v2);
  Node * l = (left == NULL) ? NULL : left->lca(v1, v2);

  return ((r != NULL) && (l != NULL))
    ? this
    : ((r == NULL) ? l : r);
}

int main()
{
  Node r(8);
  std::vector<int> v = { 4, 9, 1, 2, 3, 6, 5 };

  for (auto d : v) 
    r.insert(d);

  r.draw();

  std::cout << "----------------" << std::endl;

  Node * l;

  std::cout << "lca for 1 & 2" << std::endl;
  l = r.lca(1, 2);
  if (l != NULL) 
    l->draw();

  std::cout << "----------------" << std::endl;

  std::cout << "lca for 5 & 2" << std::endl;
  l = r.lca(5, 2);
  if (l != NULL) 
    l->draw();
}

Compilation and execution:

pi@raspberrypi:/tmp $ g++ -Wall lca.cpp 
pi@raspberrypi:/tmp $ ./a.out
  /
 9
  \
8
   /
  6
    /
   5
    \
 4
     /
    3
     \
   2
    \
  1
   \
----------------
lca for 1 & 2
   /
  3
   \
 2
  \
1
 \
----------------
lca for 5 & 2
  /
 6
   /
  5
   \
4
    /
   3
    \
  2
   \
 1
  \
pi@raspberrypi:/tmp $