Binary tree level order traversal time complexity

1
votes

HERE it is explained that method 1 of level order traversal has a time complexity of O(n^2). Can someone please explain me this. I am not sure how author is saying that printGivenLevel() takes O(n).

"Time Complexity: O(n^2) in worst case. For a skewed tree, printGivenLevel() takes O(n) time where n is the number of nodes in the skewed tree. So time complexity of printLevelOrder() is O(n) + O(n-1) + O(n-2) + .. + O(1) which is O(n^2)."

On the contrary HERE, it seems to be proved that it is O(n)

2
algorithmbinary-treetree-traversal
In the second one, it assumes the tree is balanced, the first doesn't make that assumption – genisage
But how worst case is O(n^2) .. can you please help me understand that. – Shauny
@amit's answer explains that quite well. – genisage
@amit's answer explains that quite well. [2] – Juan Lopes

2 Answers

3
votes

In the attached code, printGivenLevel() is O(n) indeed for worst case. The *complexity function) of printGivenLevel() is:

T(n) = T(left) + T(right) + O(1)
where left = size of left subtree
      right = size of right subtree

In worst case, for each node in the tree there is at most one son, so it looks something like this:

                     1
                    2
                   3
                  4
                 5
                6
               7
              8       
            ...

Now, note that the way the algorithm works, you start from the root, and travel all the way to the required level, while decreasing the level variable every time you recurse. So, in order to get to the nth level, you are going to need at least n invokations of printGivenLevel(), so the complexity function of printGivenLevel() for the above example is:

T(n) = T(n-1) + T(1) + O(1) = O(n) (can be proved used master theorem)

The first implementation requires you to do printGivenLevel() for each level, so for the same example, you get a worst case running time of O(n^2), since you need O(k) to print each level from 1 to k, which is O(1 + 2 + 3 + ... + n) =(*) O(n(n+1)/2) = O(n^2), where the equality marked with (*) is from sum or arithmetic progression

0
votes

We can perform level order traversal in an easy way with always(best,avg,worst) O(n) Time complexity.

Simple Python code:

def level_order(self):
    print(self.root.data,end=' ')
    root=self.root
    a=[root]
    while len(a)!=0:
        tmp=[]
        for i in a:
            if i.left!=None:
                tmp.append(i.left)
                print(i.left.data,end=' ')
            if i.right!=None:
                tmp.append(i.right)
                print(i.right.data,end=' ')
        a=tmp

Explanation: a is a list of all addresses of nodes at current level; tmp is a list to store addresses of child nodes of a. If len(a)=0, that means it is the last level, so the loop breaks.