Run time complexity of printing a binary tree level by level

Question

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<TreeNode> current = new LinkedList<>();
    current.add(root);

    while (!current.isEmpty()) {

        Queue<TreeNode> 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?

Answer 1

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.

Answer 2

Your algorithm is O(n), where n is the number of nodes in the tree, because you visit every node twice. That is as good as it can get. (Your code could be tidier if you visit every node once, but that wouldn't affect the performance much.)

Instead of parents and current, I suggest renaming your queues to thisLevel and nextLevel.

As @rolfl noted, iterating through a queue is an unconventional way to use a queue, because queues are designed to be accessed only at the head. Java's Queue lets you violate the queue abstraction, but that doesn't make it good practice.

If you remove each queue item as you encounter it, you should end up with an empty queue at the end of each level. You can then swap the two queues, reusing the empty queue object instead of discarding it and creating a new one.

public int printByLevel(TreeNode node) {
    if (node == null) {
        throw new IllegalArgumentException();
    }

    // Breadth-first traversal
    Queue<TreeNode> thisLevel = new LinkedList<TreeNode>(),
                    nextLevel = new LinkedList<TreeNode>();

    thisLevel.add(node);
    while (null != (node = thisLevel.poll())) {
        System.out.print(node.value + " ");

        if (node.left  != null) nextLevel.add(node.left);
        if (node.right != null) nextLevel.add(node.right);

        if (thisLevel.isEmpty()) {
            System.out.println();

            Queue<TreeNode> swapTemp = thisLevel;
            thisLevel = nextLevel;
            // We could create a new nextLevel queue, but reusing the
            // newly emptied thisLevel queue is more efficient.
            nextLevel = swapTemp;
        }
    }
}