For a Given node of a binary tree, print the K distance nodes.

For the solution, you can also refer to stackoverflow. This also tells that only one ancestor can be at K distance from a given node.

Source code: (written in C)

void K_dist_children(node * nd, int K)
{
// Base case
// The Kth child found
if(K==0)
{
printf("%d\n", nd->val);
return;
}
// K distance node from nd are at
// K-1 distance from children of current node
K_dist_children(nd->left, K-1);
K_dist_children(nd->right, K-1);
}
int K_dist_ancestor(node * cur, //curent node
node * search, //node being searched
int K)
{
// If the node is found, return back the result
if (cur == search)
{
return K-1;
}
int n1, n2;
// recursively search for the node in the tree
n1 = K_dist_ancestor(cur->left, search, K);
n2 = K_dist_ancestor(cur->right, search, K);
// PS: n1 & n2 can't be non-(-1) at the same time
// if node found in any of the sub trees
if((n1 == -1) && (n2 == -1))
return -1;
// node found in right subtree
if((n1 == -1))
{
// the current node is at distance K
if(n2 == 0)
printf("%d", cur->val);
// return back the distance
return (n2-1);
}
// node found in left subtree
if((n2 == -1))
{
// the current node is at distance K
if(n1 == 0)
printf("%d", cur->val);
// return back the distance
return (n1-1);
}
}
void print_K_distance_nodes(node * root, node * search, int K)
{
// The structure of node is:
// struct node{
// int val;
// node * left;
// node * right;
// }
// Print the ancestor at distance K
K_dist_ancestor(root, search, K);
// Print the children at distance K
K_dist_children(search, K);
}

### Like this:

Like Loading...