Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
807 B
0
Indexable
Never
Node* drive(Node *root, int &k, int node){
    if(root==NULL) return NULL;
    
    if(root->data==node) return root;
    
    Node* left =drive(root->left,k,node);
    Node* right =drive(root->right,k,node);
    
    if(left!=NULL && right==NULL) {
        k--;
        if(k<=0){
            k=INT_MAX;  //locking the ans so it  ..till now it was returning left,, 
            return root; //now it will return root at every call
        }
        return left;
    }
    
    if(right!=NULL &&left==NULL){
        k--;
        if(k<=0){
            k=INT_MAX;
            return root;
        }
        return right;
    }
    return NULL;
}

int kthAncestor(Node *root, int k, int node)
{
    Node* ans=drive(root,k,node);
    if(ans==NULL || ans->data ==node) return -1;
    else return ans->data;
    
}