Complexity of BFS in n-ary tree

Question

I am looking for algorithm to do BFS in O(n) for n-ary tree, I found the following algorithm, but I have a problem in analysing the time complexity. I am not sure if it's O(n) or O(n^2). Can someone explain the time complexity or give an alternative algorithm which run in O(n)

Thanks

breadthFirstSearch = (root, output = []) => {
  if (!root) return output;
  const q = new Queue();
  q.enqueue(root);
  while (!q.isEmpty()) {

    const node = q.dequeue();
    
    output.push(node.val);
    
    for (let child of node.children) {
      q.enqueue(child);
    }
  }
  return output;
};

score 1 · Accepted Answer · answered Jun 17 '21 at 19:55

That is indeed a BFS algorithm for a generic tree. If you define as the in -ary tree, then the time complexity is not related to that .

If however, represents the total number of nodes in the tree, then the time complexity is O() because every node is enqueued exactly once, and dequeued exactly once. As queue operations are O(1), the time complexity is O().

Complexity of BFS in n-ary tree

1 Answers1

Linked