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!