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