Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# azurkin/recursion_to_iteration.py

Last active Jun 17, 2021
 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 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 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 commented Jun 14, 2021 • edited

 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.
to join this conversation on GitHub. Already have an account? Sign in to comment