Error in finding lowest common ancestor in tree

Question

I am trying to find the lowest common ancestor of the two given values in the tree.

My approach is to traverse to the bottom left of the tree and check individual nodes weather they have both the nodes under them. The first node to give a match is the lowest common ancestor.

Can anyone tell me the error in this function.

/*
Node is defined as 

typedef struct node
{
   int data;
   node * left;
   node * right;
}node;

*/


bool find(node *root,int val)  //to check if the value exist under the given node or not
{
    if(root==NULL)
        return false;
    if(root->data==val)
        return true;

    if((root->left&&find(root->left,val))||(root->right&&find(root->right,val)))
        return true;
    return false;
}


node * lca(node * root, int v1,int v2)   //to find the lowest common ancestor
{
    if(root==NULL)
        return NULL;
    static node* ans=NULL;
    lca(root->left,v1,v2);  //traversing to the bottom of the tree
    lca(root->right,v1,v2);

    if((find(root->left,v1)&&find(root->right,v2))||(find(root->left,v2)&&find(root->right,v1)))   //checking the existence of both nodes under the tree
    {
        if(ans==NULL)
            ans=root;
    }

    return ans;  //returning the lca
}

What happens when you run the code? How does it differ from the expected result? — Frank

MartinaW MartinaW · Accepted Answer · 2017-07-08T18:20:18

Your recursive function should return only a node if the result was found. It should return NULL if the result node was not found. Break if the node was found, else continue. I would do it like this:

node * lca(node * root, int v1,int v2)   //to find the lowest common ancestor 
{
    if(root==NULL)
        return NULL;

    node* ans=NULL;

    // search the left child tree
    ans = lca(root->left,v1,v2); 
    if (ans != NULL)
      return ans; // if you found it you are finished

    // search the right child tree
    ans = lca(root->right,v1,v2);
    if (ans != NULL)
      return ans; // if you found it you are finished

    // test this tree node
    if( (find(root->left,v1)&&find(root->right,v2)) ||
        (find(root->left,v2)&&find(root->right,v1)))
    {
        // If the condition is true, this node is the result
        return root;
    }

    return NULL; // Neither this node nor any subordinate node of this node is the result 
}

Error in finding lowest common ancestor in tree

1 Answers