recursion_to_iteration.py

def dfs_postorder_recursive(root):
    if root is None:
        return  # base case
    dfs_postorder_recursive(root.left)  # LEFT
    dfs_postorder_recursive(root.right)  # RIGHT
    visit(root)  # VISIT


# T. Webster-like approach,
# which perfectly mimics recursive function execution path.
def dfs_postorder_iterative(root):
    LEFT, RIGHT, VISIT = 1, 2, 3
    stack = Stack()
    stack.push((root, LEFT))
    while len(stack) > 0:
        node, state = stack.pop()
        if node is None:
            assert state is LEFT  # just a clarification
            continue  # base case
        if state is LEFT:
            stack.push((node, RIGHT))  # next step for current node
            stack.push((node.left, LEFT))  # first step for left node
        elif state is RIGHT:
            stack.push((node, VISIT))  # next step for current node
            stack.push((node.right, LEFT))  # first step for right node
        elif state is VISIT:
            visit(node)  # finished with current node


# More common and effective,
# but (arguably) less intuitive approach.
def dfs_postorder_iterative_classic(root):
    ENTER, EXIT = 1, 2

    stack = Stack()
    stack.push((root, ENTER))

    while len(stack) > 0:
        node, state = stack.pop()
        if node is None:
            continue  # base case
        if state is ENTER:
            stack.push((node, EXIT))
            stack.push((node.right, ENTER))
            stack.push((node.left, ENTER))
        elif state is EXIT:
            visit(node)


class Node():
    """ Binary tree node """
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right


class Stack(list):
    def push(self, item):
        self.append(item)


def visit(node):
    print(node.data, end=' ')


def test(tree):
    dfs_postorder_recursive(tree)
    print()
    dfs_postorder_iterative(tree)
    print()
    dfs_postorder_iterative_classic(tree)
    print()
    print()


def test_main():
    test(None)
    test(Node(1))
    test(Node(2, Node(1)))
    test(Node(2, Node(1)))
    test(Node(2, None, Node(3)))
    test(Node(2, Node(1), Node(3)))


test_main()

Your solution provides a structure to convert all recursive traversal solutions into an iterative one. I just used the template for in-order & pre-order traversals & it works.

My intuition for your classic approach: we EXIT when we want to visit a node, we ENTER when we push items onto stack for later use (mimicking the recursive call).

Thank you so much for this!

I'm glad my code was useful. But it's just a rewriting of the example from this answer: https://stackoverflow.com/a/8512072/1632891
You may find the whole thread interesting: https://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration

Thanks! This is super helpful. I came from the SO question but found your code much cleaner. IMO the second solution is clearer and more intuitive, it's basically what I was planning to do before I went Googling thinking, gosh there has to be a simpler way!

Edit: But I see how the 3-case scenario may be more useful for understanding the general mapping from recursive to iterative functions, so it's great you have that example also.