Time complexity of level order traversal

Question

What is the time complexity of binary tree level order traversal ? Is it O(n) or O(log n)?

void levelorder(Node *n)
{    queue < Node * >q;
     q.enqueue(n);

     while(!q.empty())
      {
         Node * node = q.front();
         DoSmthwith node;
         q.dequeue();          
         if(node->left != NULL)
         q.enqueue(node->left);
         if (node->right != NULL)
         q.enqueue(node->right);
      }

}

Answer 1

Another way to approach this problem is identifying that a level-order traversal is very similar to the breadth-first search of a graph. A breadth-first traversal has a time complexity that is O(|V| + |E|) where |V| is the number of vertices and |E| is the number of edges.

In a tree, the number of edges is around equal to the number of vertices. This makes it overall linear in the number of nodes.

Answer 2

The time and space complexities are O(n). n = no. of nodes.

Space complexity - Queue size would be proportional to number of nodes O(n)

Time complexity - O(n) as each node is visited twice. Once during enqueue operation and once during dequeue operation.

This is a special case of BFS. You can read about BFS (Breadth First Search) http://en.wikipedia.org/wiki/Breadth-first_search .

Answer 3

It is O(n), or to be exact Theta(n).

Have a look on each node in the tree - each node is "visited" at most 3 times, and at least once) - when it is discovered (all nodes), when coming back from the left son (non leaf) and when coming back from the right son (non leaf), so total of 3*n visits at most and n visites at least per node. Each visit is O(1) (queue push/pop), totaling in - Theta(n).