# Recursions take O(log n) space

• It seems that the recursive calling needs O(log n) space, which is ineluctable, isn't it?

=======================

(update) Converting the recursive version to non-recursive version does not reduce space since it still need a stack to store the status.

(update) The recursive calling seems to be a top-bottom approach, but the bottom-top approaches do not help, either.

(update) Is there a constant-space solution?

(update) On Morris inorder tree traversal (@stellari): I googled the Morris traversal, and it is an inorder tree traversal without using stacks or recursion. That's really cool. Using the Morris traversal, we can convert a binary search tree to a sorted linked list with constant space. Detail explanations of the Morris traversal can be found here:
http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/

(update) Maybe the algorithm could be (pending):

1. calculate the length of the sorted list, say N;

2. construct a threaded balance tree of N nodes (without values in the nodes);

3. inorder traversal the tree, put the values in the list into the nodes;

4. delete the threads (it may take a bit more time).

=======================