Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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()
@saikatkumardey

This comment has been minimized.

Copy link

@saikatkumardey saikatkumardey commented Jun 7, 2020

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!

@azurkin

This comment has been minimized.

Copy link
Owner Author

@azurkin azurkin commented Jun 9, 2020

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

@Apollys

This comment has been minimized.

Copy link

@Apollys Apollys commented Jun 14, 2021

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment