Untitled

mail@pastecode.io avatar
unknown
c_cpp
3 years ago
1.5 kB
3
Indexable
Never
pair<BinaryTreeNode<int>*, int> findNode(BinaryTreeNode<int>* root, int key, int len){
    if(root == NULL)	return {root, len};
    
    if(root->data == key){
        return {root, len};
    }
    len += 1;
    
    pair<BinaryTreeNode<int>*, int> p1 = findNode(root->left, key, len);
    pair<BinaryTreeNode<int>*, int> p2 = findNode(root->right, key, len);
    
    if(p1.first->data == key){
        return {root, len};
    }
    if(p2.first->data == key){
        return {root, len};
    }
    return {NULL, 0};
}


void printNodesK(BinaryTreeNode<int> * root, int k){
    if(root == NULL)	return;
    
    if(k == 0){
        cout<<root->data<<" ";
        return;
    }
    printNodesK(root->left, k-1);
    printNodesK(root->right, k-1);
}


void nodesAtDistanceK(BinaryTreeNode<int> *root, int node, int k) {
    if(root == NULL)
        return;
    
    int len = 0, k2;
    
    pair<BinaryTreeNode<int>*, int> P = findNode(root, node, len);
    
    if(P.first == NULL)	return;
    
    BinaryTreeNode<int>* node = P.first;
    len = P.second;
    
    if(k > len){
        k2 = k-len;
    }
    
    if(root->data > node){
       printNodesK(node, k);
       printNodesK(root->right, k2); 
    }
    
    else if(root->data == node){
        printNodesK(root, k);
    }
    else{
       printNodesK(root->left, k2);
       printNodesK(node, k); 
    }     
    // Write your code herez
}