1
$\begingroup$

I am looking at this question from LeetCode.

There are two solutions to this question - the recursive solution and the iterative / breadth-first traversal solution.

My question is in regards to the memory requirements of each solution.

In the case of the recursive solution, we are going to be using the call stack. The call stack will, at its max, be the height of the binary tree. In a worst-case scenario, the tree is skewed, the height is the number of nodes, and our space requirement becomes linear - O(n).

In the case of the recursive solution, we use an explicit queue, instead of an implicit call stack. The largest number of elements that the call stack will hold is when the tree is a perfect binary tree (a complete binary tree has the same analysis), in which case, the queue will hold 2^h, where h is the height of the tree (indexed at 0). However, in a perfect binary tree, we also know that h = log(n + 1), so 2^h ~ 2^log(n +1), which means that the space requirements for the iterative case is O(2^(log n)).

My question is, which one of these is smaller? Can we make a determination that one of these two algorithms is better than the other in terms of memory?

$\endgroup$
2
  • 2
    $\begingroup$ $2^{log_2(n)} = n$ by definition of logarithm $\endgroup$
    – Vladislav
    Mar 10 '20 at 14:03
  • $\begingroup$ Vladislav - thank you! It was bothering me for a long time that I couldn't wrap this up! $\endgroup$
    – Steven L.
    Mar 11 '20 at 2:51
1
$\begingroup$

The obvious recursive solution (compute the maximal depth of both subtrees, add one for the root) has space complexity $O(\operatorname{depth}(T))$ (i.e., $O(\log n)$ for $n$ nodes). If you write it recursively or do the call stack by hand instead of having the language handle it for you is irrelevant.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.