Recursions take O(log n) space

  • 0

    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:

    (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).


    @Shangrila Thank you for your kind answer.

    @stellari Thank you very much for the Morris traversal. It is very cool.

  • 0

    Yes, I think so. But in a real interview, it would better for you to point it out. Asking interviwer if it can be treated as an elegant solution, or they actually want a non-recursion solution.

  • 1

    I do believe a constant space solution exist. For instance, you can use morris traversal to build the tree in O(1) space. However, this may be too much for an interview. I would say as long as you have the recursive solution and point out that it takes O(logn) space, you are probably good, unless the interviewer explicitly demands that you give an iterative solution.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.