Binary Search Tree : Lowest Common Ancestor

  • + 0 comments

    Try simple approach:

    Node *lca(Node root, int v1,int v2) { // Write your code here. Node roottemp = root; Node* arrV1[50] = {0}; Node* arrV2[50] = {0}; int index1 = 0; int index2= 0; int min =0;

        if(root == NULL)
        {
            return NULL;
        }
    
        while(root!= NULL)
        {
            if(root->data == v1)
            {
    
                arrV1[index1] = root;
                index1++;
                break;
            }
            arrV1[index1] = root; 
            root->data > v1? (root = root->left) : (root = root->right);
            index1++;
        }
    
        root = roottemp;
    
        while(root!= NULL)
        {
            if(root->data == v2)
            {
                arrV2[index2] = root;
                index2++;
                break;
            }
            arrV2[index2] = root; 
            root->data > v2? (root = root->left) : (root = root->right);
            index2++;
        }
    
        index1>index2? min = index2: min = index1;
    
        for (int i=0 ; i<min; )
        {
               if(arrV1[i] == arrV2[i])
               {
                   roottemp = arrV1[i];
                   i++;
               }
               else{
                   break;
               }
        }return roottemp;
    }
    

    }; //End of Solution