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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.