Space complexity of level order traversal traversal using a queue

Question

This is a code for level order traversal:

public void bfsTraveral() {
    if (root == null) {
        throw new NullPointerException("The root cannot be null.");
    }
    int currentLevelNodes = 0;
    int nextLevelNodes = 0;

    final Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    currentLevelNodes++;

    while(!queue.isEmpty()) {
        final TreeNode node = queue.poll();
        System.out.print(node.element + ",");
        currentLevelNodes--;
        if (node.left != null) { queue.add(node.left); nextLevelNodes++;}
        if (node.right != null) { queue.add(node.right); nextLevelNodes++;}
        if (currentLevelNodes == 0) {
            currentLevelNodes = nextLevelNodes;
            nextLevelNodes = 0;
            System.out.println();
        }
    }

In my opinion the space complexity should be O(2^h), where h is height of tree, simply because that is a max size attainable by the queue during execution. Over the internet I find the space complexity as O (n). It sounds incorrect to me. Please share your opinion.

Thanks,

Answer 1

If you think about it, in a tree with n nodes, there's no possible way that you can ever get any more than n nodes into the queue at any one time, since no node will ever be enqueued twice. This gives an immediate upper bound of O(n). This isn't a tight bound, though, since if the tree is a degenerate linked list then the memory usage will just be O(1).

Your upper bound of O(2^h) is also correct, but it's a weaker upper bound. In a tree with height h, there can be at most 2^h nodes in the bottom layer, but there's no guarantee that this is actually the case. If the tree is a degenerate linked list, the height is O(n), and your bound of O(2^h) will exponentially overapproximate the memory usage.

Therefore, your bound is correct, but O(n) is a much better bound.

Hope this helps!

Answer 2

Both O(2^h) and O(n) are correct provided it is also mentioned that the space complexity is for the Worst-case and not for the Best-case.

The confusion between O2^h and O(n) lies when it is not mentioned whether the space complexity is for Worst-case or Best-Case because the h is different for Worst-case and Best-case and can mislead in case of Best-case.

---

Worst-Case (when the tree is balanced): O(n)

When the tree is balanced, the last level will have the maximum number of nodes and that will be 2^h. And for a balanced tree, h will be log n. So O(2^h) => O(2 ^ (log n)) => O(n)

Best-Case (when the tree is a degenerate linked list): O(1)

When the tree is a degenerated linked list, every level will have a maximum of one node and thus at any point of time, there will be at most one node in the queue.