Performance of Recursive vs Iterative Solution to "Maximum Depth of a Binary Tree"

Question

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?

Answer 1

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.