## Sunday, October 21, 2012

### Nodes at same depth

Problem is to find print all the nodes at the same levels of a binary tree.Inputs given are root pointer and the pointer to the node (let it be A)whose level elements need to be printed.

Strategy:
Find the depth of the node A.
Then do a depth wise traversal of the tree by tracking the level u are at currently.
Now when u get a node of equal depth as A then print it and do a back traversal from there as other nodes from the current node will result in a higher depth. Thus we can find all the nodes at the current level.

1. Hi Plz can you give a solution for above question..Thank you

2. how can we do depth wise traversal?

3. 1.Finding depth is equivalent to finding level of the node as follows

Getting Level of a node

start from the root and level as 1. If the key matches with root’s data,
return level. Else recursively call for left and right subtrees with
level as level + 1.

int getLevelUtil(struct node *node, int data, int level)
{
if ( node == NULL )
return 0;
if ( node->data == data )
return level;
return getLevelUtil ( node->left, data, level+1) |
getLevelUtil ( node->right, data, level+1);
}
int getLevel(struct node *node, int data)
{
return getLevelUtil(node,data,1);
}
Time Complexity: O(n) where n is the number of nodes in the given Binary Tree.

2.And after that u can proceed as follows:

Print Nodes at k distance:
void printKDistant(node *root , int k)
{
if(root == NULL)
return;
if( k == 0 )
{
printf( "%d ", root->data );
return ;
}
else
{
printKDistant( root->left, k-1 ) ;
printKDistant( root->right, k-1 ) ;
}
}