Geek Answers Handbook

Temporal difficulty of level traversal

What is the time complexity of traversing binary tree order? 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); } }
+4
source share
3 answers

This is O(n) , or rather, Theta(n) .

Look at each node in the tree - each node is “visited” no more than 3 times and at least once) - when it is detected (all nodes), when returning from the left son (non leaf), and when returning from the right son (non leaf), so that the total number of 3 * n visits is the largest and n visits, at least on node. Each visit is O(1) (queue push / pop), the summation is in Theta(n) .

+6
source

The complexity of time and space is O (n). n = no. nodes.

The complexity of the space - the size of the queue will be proportional to the number of nodes O (n)

The time complexity is O (n), since each node is visited twice. Once during a queue operation and once during a decompression operation.

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

0
source

Another way to approach this problem is to determine that bypassing the level order is very similar to a broad search at the beginning of the chart. The first pass has a time complexity that is O(|V| + |E|) , where |V| is the number of vertices, and |E| - number of ribs.

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

0
source

More articles:


All Articles