Binary tree post order iterative traversal

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)]
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s