Print all nodes at distance K from given node

#1

One test case is not getting passed. please tell where my code is incorrect.
Following is the link of the code:-

#2

@krikhi You have written a very complicated code to understand. This is a simple bfs traversal question which you can solve by traversing to the kth level in the tree

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#4

bfs is done to find the nodes at distance k in the same subtree but which approach we can use for the nodes present in another subtree at distance K

#5

Hi @krikhi, Let me share my approach,

let’s call the given node as X
There are two types of nodes that we need to consider

the nodes that are k distance below X (desendants at distance k from X)
the nodes that are k distance above X or in some other subtree
for (1) we can easily find the required nodes by using recursive call to the child nodes and decrementing value of k

for (2) things are just a bit complex for every ancestor say Y, of X we need to to find the distance of Y from X say d, then we need to go to the other subtree (i.e. the subtree in which X does’nt belong i.e. if X is in left Subtree of Y then consider right subtree and vice versa) and find all nodes at k-d distance from Y

Here is the code snippet

/* Recursive function to print all the nodes at distance k in the 
   tree (or subtree) rooted with given root. See  */
void printkdistanceNodeDown(node *root, int k) 
{ 
    // Base Case 
    if (root == NULL || k < 0)  return; 
  
    // If we reach a k distant node, print it 
    if (k==0) 
    { 
        cout << root->data << endl; 
        return; 
    } 
  
    // Recur for left and right subtrees 
    printkdistanceNodeDown(root->left, k-1); 
    printkdistanceNodeDown(root->right, k-1); 
} 
  
// Prints all nodes at distance k from a given target node. 
// The k distant nodes may be upward or downward.  This function 
// Returns distance of root from target node, it returns -1 if target 
// node is not present in tree rooted with root. 
int printkdistanceNode(node* root, node* target , int k) 
{ 
    // Base Case 1: If tree is empty, return -1 
    if (root == NULL) return -1; 
  
    // If target is same as root.  Use the downward function 
    // to print all nodes at distance k in subtree rooted with 
    // target or root 
    if (root == target) 
    { 
        printkdistanceNodeDown(root, k); 
        return 0; 
    } 
  
    // Recur for left subtree 
    int dl = printkdistanceNode(root->left, target, k); 
  
    // Check if target node was found in left subtree 
    if (dl != -1) 
    { 
         // If root is at distance k from target, print root 
         // Note that dl is Distance of root's left child from target 
         if (dl + 1 == k) 
            cout << root->data << endl; 
  
         // Else go to right subtree and print all k-dl-2 distant nodes 
         // Note that the right child is 2 edges away from left child 
         else
            printkdistanceNodeDown(root->right, k-dl-2); 
  
         // Add 1 to the distance and return value for parent calls 
         return 1 + dl; 
    } 
  
    // MIRROR OF ABOVE CODE FOR RIGHT SUBTREE 
    // Note that we reach here only when node was not found in left subtree 
    int dr = printkdistanceNode(root->right, target, k); 
    if (dr != -1) 
    { 
         if (dr + 1 == k) 
            cout << root->data << endl; 
         else
            printkdistanceNodeDown(root->left, k-dr-2); 
         return 1 + dr; 
    } 
  
    // If target was neither present in left nor in right subtree 
    return -1; 
}

You can try to implement it . In case of any doubt feel free to ask :slight_smile:
If you got the answer then mark your answer as resolved

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.