I’m feeling bothered with the current tree search implementations I’ve found online. I think they are confusing and more difficult than they should be. People state that iterative post order is the “hardest of the three iterative DFS”, while the three implementation are supposed to be at least somewhat orthogonal.
So, here is my implementation of a post order iterative traversal. The idea is that we use a stack to store a program. The program has 3 parts, processing the left and right nodes and processing the current node, just like the contents of the recursive function. We also store context information to know what to do in each part of the program, again, like the recursive function: for children, we do the recursion (add a new program in the stack), for the current node, we process it.
#!/usr/bin/env python class Tree: def __init__(self, val, left=None, right=None): self.left = left self.val = val self.right = right def postorder(self): stack = [(self.val, False), (self.right, True), (self.left, True)] while len(stack) != 0: data, is_tree = stack.pop() if not is_tree: print(data) continue if data is None: continue stack += [(data.val, False), (data.right, True), (data.left, True)] if __name__ == '__main__': t = Tree(1, Tree(2, Tree(3), Tree(4)), Tree(5, None, Tree(6))) t.postorder()
To implement the inorder and preorder versions, just change the relative position of self.val when inserting a new program in the stack.
stack += [(data.right, True), (data.val, False), (data.left, True)]
stack += [(data.right, True), (data.left, True), (data.val, False)]