Complexity of Level Order traversal

Question

Function to print a particular level

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

Function to print all level order traversal

void printLevelOrder(struct node* root)
{
   int h = height(root);
   int i;
   for(i=1; i<=h; i++)
      printGivenLevel(root, i);
}

Here I want to calculate complexity of function printLevelOrder(). The resource from where I was referring it said it runs in O(n²). I can't figure out how.
Because if I apply master's subtraction theorem to calculate complexity of method 1 it comes 2ⁿ as T(n)=2⋅T(n-1)

Please correct me, if I am approaching wrong somewhere.

i can help with the formatting part :) if you are on chrome, heres an handy [Chrome ext.](https://chrome.google.com/webstore/detail/stackoverflow-code-beauti/pljeafjjkkbacckkollfejkciddacmeb) else this post has heaps of [online formatters](http://stackoverflow.com/a/4735078/4749156). — daxeh, Apr 27 '15 at 18:53

score 0 · Answer 1 · answered Apr 27 '15 at 18:35

0

Assume that we have a skewed tree with n nodes. Something like :

1 \ 2 \ 3 \ 4 . . n

Now this tree has n levels. For each level i you call printGivenLevel(i) which goes through all nodes from level 1 through level i to finally print the node on level i.

So for level n you go through n nodes taking cn time. For level n - 1 you go through n - 1 nodes taking c(n - 1) time and so on.

So total time = c(n + (n - 1) + (n - 2) + .... + 3 + 2 + 1) ~ cn² = O(n²)

answered Apr 27 '15 at 18:35

user1925405

332
1
5
13

Sorry I got what were you trying to say. But why it fails when I try to approach it through Master's Subtraction theorem. – Atul Yadav Apr 28 '15 at 07:53
I think the recurrence relation you wrote might be wrong. For the case I illustrated above, the recurrence would be T(n) = T(n - 1) + c. From what I can gather, you wrote a recurrence with a kind of complete binary tree in mind -> 2 * T(n - 1), with the 2 being -> 1 for left child + 1 for right child, right ? If that is the case then number of nodes is no longer n - 1 in the recursive call. It is rather ~ n / 2. So more like T(n) = 2T(n / 2) + c – user1925405 Apr 30 '15 at 07:49

Complexity of Level Order traversal

1 Answers1