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.

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.

__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.

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

ReplyDeletehow can we do depth wise traversal?

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

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

}

}

Follow the link:

http://sudhansu-codezone.blogspot.in/2011/12/isbst.html