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