CODEWITHSUNDEEP
c++data-structurestree
sam fisher
sam fisher

Reputation: 183

Error in finding lowest common ancestor in tree

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
}

Upvotes: 1

Views: 97

Answers (1)

MartinaW
MartinaW

Reputation: 111

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 
}

Upvotes: 1

Related Questions