What is space complexity for breadth-first search on a binary tree?

Question

Here is my Java solution for printing a binary tree level by level with breadth first search(it works!!)

public void printByLevel() {
    System.out.print("Elements By Level:");
    if(overallRoot!= null) {
        Queue<IntTreeNode> bfs = new LinkedList<IntTreeNode>();
        bfs.add(overallRoot);
        while(!bfs.isEmpty()) {
            IntTreeNode root = bfs.remove();
            System.out.print(" " + root.data);
            if(root.left!=null) 
                bfs.add(root.left);
            if(root.right!=null)
                bfs.add(root.right);
        }
    }
    System.out.println();
}

I know with my breadth-first search algorithm, I will visit all the nodes in the tree so the time complexity of the algorithm will be O(n).

I am having trouble with analyzing the space complexity of my solution though. I learned from Space Complexity that when analyzing space complexity, you have to take into account the space you allocate from the heap and the stack

Here, I am not making any recursive calls so the space complexity will just be the space I allocated for the queue for breadth-first-search. I read from here BFS Complexity that the space complexity of breadth first search is O(V) where V is the number of vertices.

Does that same space complexity apply to my tree variation? I have yet to produce a test case in which the BFS queue will hold all the nodes in the tree. Even when the binary tree degenerates to a linked list like in the following pictorial that I got from BST, where normal operations on a tree take O(n) time and O(n) space, the BFS queue will hold at most 1 element.

Can anyone give me a test case in which the BFS queue will hold all the nodes in tree, proving that the space complexity is O(n)?

anatolyg anatolyg · Accepted Answer · 2015-03-29T21:39:53

Consider the "full" or "perfect" binary tree:

     .
   / .
  0  .
 / \ .
0    .
 \ / .
  0  .
   \ .
     .

At the last iteration, the queue will hold roughly half of the nodes in the tree, so the complexity is O(n/2), which is the same as O(n).

What is space complexity for breadth-first search on a binary tree?

1 Answers