Posted tagged ‘recursively search’

K distance nodes in a Binary tree

February 3, 2012

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

%d bloggers like this: