Converting recursive algorithm to iterative with stacks

Question

My professor gave this exercise to us in class and asked to exactly mimic the recursive calls with stacks. This is the recursive algorithm:

def algo(T, h):
    ret = -1
    s = 0
    d = 0

    if T != None:
        if T.left != None:
            s = algo(T.left, h + 1)
        if T.right != None:
            d = algo(T.right, h + 1)

        if s == 0 and d == 0:
            ret = h
        else:
            ret = s + d

    return ret

This is my attempt at solving this exercise (I used two stacks, one for saving T and another one to save "s")

def algo_it(T, h):
    ret = -1
    s = 0
    d = 0

    curr = T
    next = None
    last = None

    stack_T = Stack()
    stack_S = Stack()

    while curr != None or not stack_T.empty():
        if curr != None:
            # First time entering the function
            ret = -1
            s = 0
            d = 0

            if curr.left != None:
                # Left recursive call
                h = h + 1
                next = curr.left

                # Save current T because it will be popped when going up
                # on recursion tree
                stack_T.push(curr)
            elif curr.right != None:
                # Right recursive call
                h = h + 1
                next = curr.right

                stack_T.push(curr)
            else:
                # Force going up on recursion tree
                next = None
        else:
            # Coming up from recursion tree
            curr = stack_T.top()

            if last != curr.right and curr.right != None:
                # We're here from the 1st recursive call (left)
                # We have to go in right recursive call now
                h = h + 1
                next = curr.right

                # We are returning from left, so ret = s = algo(T.left, h + 1)
                s = ret
                stack_S.push(s)

                ret = -1
                d = 0
            else:
                stack_T.pop()

                if curr.right != None:
                    s = stack_S.pop()
                    d = ret
                else:
                    s = ret
                    d = 0

                if s == 0 and d == 0:
                    ret = h
                else:
                    ret = s + d

        last = curr
        curr = next

    return ret

The algorithm is failing because on stack_S.pop() I'm popping when stack is empty so I get runtime error. Am I close to get a solution?

I highly appreciate all of your help!

Answer 1

When you are mimicking the recursive call, you are only pushing on the stack that you know you are supposed to return to. But you aren't pushing the context to know which one to push the response to.

I would suggest that you do this problem in multiple steps.

1. Convert all of your function local variables (T, h, ret, s and d) into stacks outside of your recursive function, with explicit pop/push instead of declaring them, and expecting them to disappear when your function ends. (Hint: leave ret on the stack, and pop off of it as you manipulate stack_s or stack_d.) This may require creating a helper function for the very first recursive call.
2. Put labels in your function for where you first call it, and every place that you can return.
3. Convert to iterative as follows. Add a stack for the function calls. It will contain a label for where to be in the function. Instead of making a recursive call you change the top of the function stack to say where to return to in this call, and push a new one on to say start a new function, and then go to the next loop iteration. (The condition for exiting the loop is that the function stack is empty, and your answer will be the top of the ret stack.)

This is a somewhat lengthy but mechanical process. It should give you an appreciation for how much the computer just does for you normally. :-)