Print all nodes at distance k from a given node

#1

what approach or logic is to be used while maintaining or tracking the distance?

#2

basically here, you need to create a function as : print_at_distance(root,target,k);
where target is the target node…
Thus, you will have two kinds of nodes,
Nodes in the subtree rooted with target node.
Other nodes, may be an ancestor of target, or a node in some other subtree.

if(root->data==target)
{
    print_k_distance_down(root,k);
    return 0;
}

This is for the target nodes …
For other kinds of nodes you need to calculate the distance from the target node as :
int dl=print_at_distance(root->left,target,k);
similarly, you will have to calculate for right as well.

#3

it is really not very clear how is the function being implemented,could you please elaborate the functons?

#4

Basically, you will make the function as , print_at_distance(root,target,k), which you will use in the main function…
int print_at_distance(node *root,int target,int k)
{
if(root==NULL)
{
return -1;
}
if(root->data==target)
{
print_k_distance_down(root,k);
return 0;
}
int dl=print_at_distance(root->left,target,k);
if(dl!=-1)
{
if(dl+1==k)
v.push_back(root->data);
else
print_k_distance_down(root->right,k-dl-2);
return 1+dl;
}
// similar code you will use for right values as well…

// the above function has a function call of subsidiary function : print_k_distance_down(root,k);

void print_k_distance_down(node *root,int k)
{
if(root==NULL || k<0)
{
return;
}
if(k==0)
{
v.push_back(root->data);
return;
}
print_k_distance_down(root->left,k-1);
print_k_distance_down(root->right,k-1);
}

I hope you get a rough idea on the functions you need to build in your code…

#5

Since you arent replying, I am marking this doubt as resolved. You can reopen it if you still face any issue with the code.