Run time complexity of printing a binary tree level by level

I have some doubts about running time of following question. The problem is printing a binary tree level by level. For example if tree is like

5
           / \
          2   6
         / \   \
        7   1   8

Then the output should be like

5
2 6
7 1 8

TreeNode structure is very simple and looks like below;

public class TreeNode {

    public TreeNode left;
    public TreeNode right;
    public int      value;

    public TreeNode(int value) {
        this.value = value;
    }
}

And the code is shown below:

public void printByLevel(TreeNode root) {

    if (root == null) {
        throw new IllegalArgumentException();
    }

    Queue current = new LinkedList<>();
    current.add(root);

    while (!current.isEmpty()) {

        Queue parents = current;
        current = new LinkedList<>();

        // print parents
        for (TreeNode parent : parents) {
            System.out.print(parent.value + "  ");
        }

        System.out.println();

        // construct next level by adding children of each parent
        for (TreeNode parent : parents) {

            if (parent.left != null) {
                current.add(parent.left);
            }

            if (parent.right != null) {
                current.add(parent.right);
            }
        }
    }
}

Now can I say running time of this algorithm is \$O(N)\$ because every is node processed only once? Or should I say it is \$O(m*N)\$, where \$m\$ refers to number of nodes at the current level because I am printing nodes at each level?

Your algorithm is plain \$O(n)\$. If you double the number of nodes, your runtime doubles. If you double the number of nodes at the current level, you also double the total number of nodes (or are you planning an unbalanced tree?).

Your algorithm is OK, but there are some deviations from the classics...

The use of a queue here is not quite right, or, rather, the way you are using it is not taking advantage of its queue features. In fact, you are using it as a List, and not a Queue. A Queue should be using the methods add, remove and element (or offer, poll, and peek). You are using the iterate method though instead.

Also, instead of emptying the queue, you create a new one, and throw the old one out. This is inefficient.

A more traditional implementation of the algorithm will use a single queue, and add a 'marker' in the queue to indicate the end of a 'row' in the tree.

Consider using 'null' as a marker, to show you have reached the end of the row, as follows:

queue.add(root);
queue.add(null);
while (!queue.isEmpty()) {
    Node n = queue.remove();
    if (n == null) {
        // end of a row
        System.out.println();
        // which also means we have no more kids to add, so
        // if there is more data, we mark the next end of the *next* row:
        if (!queue.isEmpty()) {
            queue.add(null);
        }
    } else {
        System.out.print(n.value + "  ");
        if (n.left != null) {
            queue.add(n.left);
        }
        if (n.right != null) {
            queue.add(n.right);
        }
    }
}

Sometimes people use a special marker instance instead of null, perhaps something like:

private static final ENDOFROW = new Node(-1);

Then, instead of the null check, you can do:

if (n == ENDOFROW) {

and you can 'add' an ENDOFROW instance as well instead of the null.

StackExchange Code Review Q#62242, answer score: 8