3
void level_order_recursive(struct node *t , int h) //'h' is height of my binary tree
{                                                 //'t' is address of root node
    for(int i = 0 ; i <= h ; i++)  
    {
        print_level(t , i);
    }
}

After print_level() is called everytime , I think recursive function is called (2^i) times . So 2^0 + 2^1 + 2^2 ....2^h should give time complexity of O(2^n).Where am I going wrong ?

void print_level(struct node * t , int i)
{
    if( i == 0)
        cout << t -> data <<" ";
    else
        {
            if(t -> left != NULL)
                print_level(t -> left , i - 1);   //recursive call
            if(t -> right != NULL)
                print_level(t -> right , i - 1); //recursive call
        }
}
meJustAndrew
  • 6,011
  • 8
  • 50
  • 76
Nishant_123
  • 89
  • 6
  • What is the "data" you are printing here: cout << t -> data <<" "; ? should it be complexity values? Also, why do you think you are wrong? It's indeed O(2^n) from your calculation. – meJustAndrew Jun 25 '16 at 11:08
  • @meJustAndrew Its an integer data . That is defined in node structure that I have not mentioned here . Its recursive version of Level order traversal of a binary tree. Time complexity of this code is supposed to be O(n^2). Can you please check it out [here](http://www.geeksforgeeks.org/level-order-tree-traversal/) – Nishant_123 Jun 25 '16 at 11:17

4 Answers4

3

You are confusing h and n. h is the height of the tree. n is apparently the number of elements in the tree. So print_level takes worst case O ($2^i), but that is also just n.

The worst case happens when you have a degenerate tree, where each node has only one successor. In that case you have n nodes, but the height of the tree is also h = n. Each call to print_level takes i steps in that case, and summing up i from 1 to h = n gives O ($n^2).

gnasher729
  • 51,477
  • 5
  • 75
  • 98
2

You always start at the root of the tree t and increase the level by one each time (i) until you reach the height of the tree h.

You said it is a binary tree, but you did not mention any property, e.g. balanced or so. So I assume it can be an unbalanced binary tree and thus the height of the tree in worst case can be h = n where n is the number of nodes (that is a completely unbalanced tree that looks like a list actually).

So this means that level_order_recursive loops n times. I.e. the worst case is that the tree has n levels.

print_level receives the root node and the level to print. And it calls itself recursively until it reaches the level and prints out that level.
I.e. it loops i times (a recursive call decreases i by one each time).

So you have 1 + 2 + 3 + ... + h iterations. And since h = n you get 1 + 2 + 3 ... + n steps. This is (n * (n+1))/2 (Gaussian sum formula) which is in O(n^2).

If you can assure that the tree is balanced than you would improve the worst case scenario, because the height would be h = ld(n) where ld denotes the binary logarithm.

Ely
  • 10,860
  • 4
  • 43
  • 64
2

Based on this or that, pages 3 and 4, binary search algorithm, which resembles our case, has a time complexity of T(n) = T(n/2) + c. Except that, both left and right sub-trees are browsed, hence the 2T(n/2) in the formula below, since this is a traversal algorithm, rather than a search one.

Here, I will comply to the question and use 'h' instead of 'n'.

Using recurrence relation, you get the following proof:

enter image description here

Mohamed Ennahdi El Idrissi
  • 2,931
  • 2
  • 19
  • 32
1

In the worst case the time complexity will be O(n^2) but cannot be 2^n as time complexity for each level will be-> O(n) + O(n-1) + O(n-2) + ... + O(1) which is at worst O(n^2).

Anant_Kumar
  • 764
  • 1
  • 7
  • 23