Bazaarvoice Interview Question Software Engineer / Developers
b_level(root,k)
{
if(k==0)
printf(root->value)
else
{
b_level(root->left,k-1);
k--;
b_level(root->right,k);
}
}
int main()
{
for(k=0,k<h;k++) //h is hgt of tree
{
b_level(root,k);
}
return;
}
this is the code given in NI paper on 14 sep in NITK, surathkal
they asked to find what code is doing.. it is printing all nodes at kth level. you can trace.
How about this approach::
Root Level to begin with is 0. And 'desired' level is depth at which we wish to
print the node values
printAtDesiredLevel(node *root,int level,int desired)
{
if(!root)return
else if(level==desired)
{
printf("%d",root->value)
return
}
printAtDesiredLevel(root->left,level+1,desired)
printAtDesiredLevel(root->right,level+1,desired)
}
void main()
{
printAtDesiredLevel(root,0,<desiredLevelValue>)
}
You algorithm for printing a level is equivalent to the earlier one copied from NI. Your main() is the correct solution to the original problem, since it prints ONLY the desired level, whereas the NI main() prints all the levels UP TO (and including) the level specified.
Couldn't you optimize your algorithm by doing a level++ once before the left/right traversal, or even ++level in the left traversal? Just think how many clock cycles it would save!! Just kidding, I have a disease that makes me spot these things.
It might make it a bit more readable, although yours is already much more readable compared to the NI code that uses k-1 in the left traversal, then decrements (k--), then uses k (now decremented) in the right traversal.
bfs or dfs, but keeping track of the current level - dont go past level x and only print items at level x.
- anon September 28, 2009