What is the time complexity of N-ary Tree Level Order Traversal. Is it always O(N) irrespective of no. of loops used?

Question

Let us consider the following code. I am trying to create a resultant vector containing each level of an n-ary tree in a separate inner vector. What can be time complexity for the following code?

// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*>q;
        q.push(root);
        vector<vector<int>> v;  //Resultant vector
        vector<int> inn;        //inner vector
        if(!root){
            return v;
        }
        inn.push_back(root->val);
        while(!q.empty()){
            int qn=q.size();
            v.push_back(inn);
            inn.clear();
            for(int i=0;i<qn;i++){
                Node* cur=q.front();
                if((cur->children).size()){
                    for(auto child:cur->children){
                        q.push(child);
                        inn.push_back(child->val);
                    }
                }
                q.pop();
            }
        }
        return v;
    }
};

How can we evaluate the time complexity as O(N) incase of multiple nested loops? Here N is the no. of nodes in the tree.

Answer 1

The time complexity is indeed O(N). There is no rule that code with nested loops could not have such time complexity.

Consider that every node is added exactly once to the queue q and is removed exactly once from the queue q.

Although the innermost for loop may look like it might make the time complexity non-linear, this is not true: one iteration of that loop will always deal with a different child node, and we know there are only N of those.

We can also observe that the innermost for loop often doesn't iterate at all. This is the case for leaves in the tree. This may help to make it intuitively acceptable that this is indeed an algorithm that has linear time complexity.