nonRecursiveTraversalOfBinaryTree.py

# Given a balanced binary tree like this:
#         1
#        / \
#       2   3
#      / \ / \
#     4  5 6  7
#
# Sample Output:
# 1. preorder traversal: 1 2 4 5 3 6 7
# 2. inorder traversal: 4 2 5 1 6 3 7
# 3. suborder traversal: 4 5 2 6 7 3 1


class BalancedBinaryTree(object):

    def __init__(self, list):
        self.list = list

    def isOutOfIndex(self, nodeIndex):
        if nodeIndex < 0 or nodeIndex > len(self.list) - 1:
            return True
        else:
            return False

    def isExistingLeftChild(self, nodeIndex):
        if self.isOutOfIndex(nodeIndex):
            print "Out of Index"
            raise
        leftChildIndex = nodeIndex * 2 + 1
        if leftChildIndex > len(self.list) - 1:
            return False
        else:
            return True

    def getLeftChild(self, nodeIndex):
        if self.isExistingLeftChild(nodeIndex):
            leftChildIndex = nodeIndex * 2 + 1
            return leftChildIndex
        else:
            print "No Left Child"
            raise

    def isExistingRightChild(self, nodeIndex):
        if self.isOutOfIndex(nodeIndex):
            print "Out of Index"
            raise
        leftChildIndex = nodeIndex * 2 + 2
        if leftChildIndex > len(self.list) - 1:
            return False
        else:
            return True

    def getRightChild(self, nodeIndex):
        if self.isExistingRightChild(nodeIndex):
            rightChildIndex = nodeIndex * 2 + 2
            return rightChildIndex
        else:
            print "No Right Child"
            raise

    def visit(self, nodeIndex):
        if self.isOutOfIndex(nodeIndex):
            print "Out of Index"
            raise
        return self.list[nodeIndex]


def preorderTraversal(tree):
    seq = []
    node = 0
    stack = []
    stack.append(node)
    while len(stack) > 0:
        # for every sub tree presented by the top of the stack
        node = stack.pop()
        # firstly, visit the root node of the subtree
        seq.append(tree.visit(node))
        # as the right child is in the latter order, push the
        # right child into the stack first.
        if tree.isExistingRightChild(node):
            stack.append(tree.getRightChild(node))
        # then push the left child into the stack
        if tree.isExistingLeftChild(node):
            stack.append(tree.getLeftChild(node))
    return seq


# def inorderTraversal(tree, node=0, seq=[]):
#     if not tree.isExistingRightChild(node):
#         seq.append(tree.visit(node))
#         return
#     if tree.isExistingLeftChild(node):
#         inorderTraversal(tree, tree.getLeftChild(node), seq)
#     seq.append(tree.visit(node))
#     if tree.isExistingRightChild(node):
#         inorderTraversal(tree, tree.getRightChild(node), seq)
#     return seq

# def inorderTraversal(tree):
#     seq = []
#     node = 0
#     pre = -1
#     stack = [node]
#     while len(stack) > 0:
#         node = stack.pop()
#         if tree.isExistingLeftChild(node):
#             if pre < tree.getLeftChild(node):
#                 stack.append(node)
#                 node = tree.getLeftChild(node)
#                 stack.append(node)
#                 continue
#         seq.append(tree.visit(node))
#         pre = node
#         if tree.isExistingRightChild(node):
#             node = tree.getRightChild(node)
#             stack.append(node)
#     return seq

def inorderTraversal(tree):
    seq = []
    node = 0
    stack = []
    stack.append(node)
    while len(stack) > 0:
        # go to the left most child first
        if not node is None:
            while tree.isExistingLeftChild(node):
                stack.append(tree.getLeftChild(node))
                node = tree.getLeftChild(node)
        # visit the left most child
        # or visit an intermedia node
        node = stack.pop()
        seq.append(tree.visit(node))
        # if the tree is not a leaf and has right child
        if tree.isExistingRightChild(node):
            node = tree.getRightChild(node)
            stack.append(node)
        else:
            # there is no right child, set a flag to move backward
            node = None
    return seq


def postorderTraversal(tree):
    seq = []
    node = 0
    pre = -1
    stack = []
    stack.append(node)
    while len(stack) > 0:

        # move to the left most child
        if not node is None:
            while tree.isExistingLeftChild(node):
                node = tree.getLeftChild(node)
                stack.append(node)
        # point to the left most child
        # or an intermedia node
        node = stack.pop()
        # if it has right child and not traversed
        if tree.isExistingRightChild(node) and not pre == tree.getRightChild(node):
            # pushing back the node into the stack
            stack.append(node)
            # as well as pushing back right child into the stack
            node = tree.getRightChild(node)
            stack.append(node)
        else:
            # if it has no need to traverse children, traverse himself
            seq.append(tree.visit(node))
            pre = node
            node = None
    return seq

if __name__ == '__main__':
    tree = BalancedBinaryTree([1, 2, 3, 4, 5, 6, 7, 8])
    seq = inorderTraversal(tree)
    print seq