complexityrecursiontrees
Recursion uses space even without extra arrays
Anonymous
A recursive call keeps its state on the call stack. For a traversal with maximum depth h, stack space can be O(h), even if the algorithm creates no extra collection. Check the worst-case depth before choosing recursion for a very skewed tree.
0