What's the time complexity of this BFS alg that returns a 2D ArrayList?

Question

I'm trying to figure out what time complexity this method would be to get better at computing time complexities. I was told by someone else that this would be a worst case O(n^2) (n being elements in the tree) but I'm confused since the outer while loop would only go the amount of levels, not total elements.

Any help would be great!

public List<List> returnLevelOrder(TreeNode root) { <List<List> ret = new ArrayList<List> ();

Queue<Integer> queue = new List<Integer>();

if(root==null){
    return ret;
}

queue.add(root);

while(!queue.empty()) {

    ArrayList<Integer> level = new ArrayList<Integer>();

    int levelSize = queue.size();

    while(levelSize >0) {
        TreeNode currNode = queue.poll();
        level.add(currNode.val);
        levelSize--;

        if(currNode.left != null) {
            queue.add(currNode.left.val);
        }

        if(currNode.right != null) {
            queue.add(currNode.right.val);
        }

    }
    ret.add(level);

}

return ret;

}

Answer 1

It is O(n) - you visit all the elements once - it is an iterative tree traversal.