Space complexity of breadth first search of binary tree?

2
votes

What would be the space complexity of breadth first search on a binary tree? Since it would only store one level at a time, I don't think it would be O(n).

1
algorithm
If a tree is balanced, it will have ~n/2 leaves so the last level will have O(n) size. – hilberts_drinking_problem
@hilberts_drinking_problem - please turn that into an answer so OP can approve at will. – shapiro yaacov

1 Answers

4
votes

The space complexity is in fact O(n), as witnessed by a perfect binary tree. Consider an example of depth four:

                  ____________________14____________________
                 /                                          \
         _______24_________                        __________8_________
        /                  \                      /                    \
     __27__             ____11___             ___23___              ____22___
    /      \           /         \           /        \            /         \
  _4        5        _13         _2        _17        _12        _26         _25
 /  \      / \      /   \       /  \      /   \      /   \      /   \       /   \
29   0    9   6    16    19    20   1    10    7    21    15   18    30    28    3

Note that the number of nodes at each depth is given by

depth num_nodes
0     1
1     2
2     4
3     8
4     16

In general, there are 2^d nodes at depth d. The total number of nodes in a perfect binary tree of depth d is n = 1 + 2^1 + 2^2 + ... + 2^d = 2^(d+1) - 1. As d goes to infinity, 2^d/n goes to 1/2. So, roughly half of all nodes occur at the deepest level. Since n/2 = O(n), the space complexity is linear in the number of nodes.

The illustration credit goes to the binarytree package.