## K distance nodes in a Binary tree

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); }

Advertisements

**Explore posts in the same categories:**Uncategorized

**Tags:** binary tree, C, c sourcecode, interview, nodes, recursively search

## Leave a Reply