Why does this level order traversal run in O(n) time?

user_7183221 0
Viewed 181
    vector<vector<int>> levelOrder(TreeNode* root) {

        queue<TreeNode*> bfs;
        if (root != nullptr) bfs.push(root);
        vector<vector<int>> sol;
        vector<TreeNode*> temp; 
        vector<int> indivSol;
        
        while (!bfs.empty()) {
            
            int currSz = bfs.size();
            for (int i = 0; i < currSz; i++) {
                temp.push_back(bfs.front());
                bfs.pop();
                
                indivSol.push_back(temp.at(i)->val);                

                if (temp.at(i)->left != nullptr) bfs.push(temp.at(i)->left);
                if (temp.at(i)->right != nullptr) bfs.push(temp.at(i)->right);
            }
            
            temp.clear();
            sol.push_back(indivSol);
            indivSol.clear();
            
        }
        
        return sol;
    }

I know that the outer while loop will run n times (n being the number of nodes in the tree), but will the inner for loop make the solution run in O(n^2) time? Since a tree has at most 2^n nodes at level n, currSz can grow for each iteration of the outer loop from 1 to 2 to 4 to 8 to 16 ...

EDIT: realized that the outer loop will only run l many times where l is the number of levels

big-o algorithm c++
3 Answers

Forget everything, just recall that when you are performing level order traversal using this code, you visit every node once. So, if in total there are k nodes in the tree then the time complexity will be O(k).

h : height of the tree

The while loop runs h times and at every iteration (i.e at every level) it traverses over all the nodes present in that level. So similarly this goes for every iteration (level) which results in O(n) (n is total no of nodes)

user_107586540

Another way to look at the problem as a special version of Breadth first search.

In BFS you visit the adjacencies for each node (making sure not to enter in a loop). This means the total cost is the sum of all adjacencies which is the number of edges for direct graph and twice the number of edges for an undirected graph.

In a tree each node has a unique parent so the number of edges is equal to the number of nodes minus one, hence the O(n) cost.

user_135057600

Use amortized runtime analysis to understand why this is O(n).

In short, amortized analysis works to bound runtime by establishing a bound on the number of times data (or some other resource) is manipulated as opposed to the absolute number of atomic operations that occur (overly pessimistic.)

Normally with BFS you need a data structure to track which nodes have been visited, but this seems to be acting on a tree which ensures each node will be visited only once (since each node has a unique and only one parent in traversal.) Given this algorithm does a constant number of operations per each node visit this is O(n).

The fact there are nested loops is a red herring as through this analysis you can guarantee it is O(n).

user_1779310
Related