I am looking at this question from LeetCode.
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 -
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
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
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?