anuj.aj07
BAN USER- 0of 0 votes
AnswersBinary tree level order traversal with each level is print on different line. i gave the solution by calling print fucntion for each level. but i got stuck in derive the time complexity analysis . pls tell me time complexity ananlysis
- anuj.aj07 in India| Report Duplicate | Flag | PURGE
iLabs Software Engineer / Developer
for each level i am traversing the all the nodes till d-1 level.
so if height of the tree is h
level 0 --root node will be traverse h+1 time
level-1--- h time
level h ----- 1 time
so it will be like
(h+1) + 2 h + 2^1 (h-1) + 2^2 (h-2) +...........2^h
how to solve this now
my solution was
void printLevelOrder(struct node* root)
{
int h = height(root);
int i;
for(i=1; i<=h; i++)
printGivenLevel(root, i);
}
void printGivenLevel(struct node* root, int level)
{
if(root == NULL)
return;
if(level == 1)
printf("%d ", root->data);
else if (level > 1)
{
printGivenLevel(root->left, level-1);
printGivenLevel(root->right, level-1);
}
}
what will be complexity in case of balance binary tree .
in worst case it will be O(n)
hi this is written test ques or interview.....if u have given java written can u pls give me some idea bcz i have java written test and interview next week...........
- anuj.aj07 May 08, 2013