In order traversal of a tree

in_order_traversal.py

def in_order_recursive(input, index):
    if index >= len(input) or input[index] == None:
        return
    in_order_recursive(input, (index * 2) + 1)
    print input[index],
    in_order_recursive(input, (index * 2) + 2)
        
in_order_recursive([3,2,1,1,1,1,0,1,0], 0)
# 1 1 0 2 1 3 1 1 0

def in_order(input):
    parent_stack = []
    current = 0
    parent_stack.append(current)
    while len(parent_stack) > 0:
        left = (current * 2) + 1
        if left < len(input) and input[left] is not None:
            parent_stack.append(current)
            current = left
        else:
            print input[current],
            current = parent_stack.pop()
            right = (current * 2) + 2
            if right < len(input) and input[right] is not None:
                if len(parent_stack) > 0:
                    print input[current],
                current = right

in_order([3,2,1,1,1,1,0,1,0])
# 1 1 0 2 1 3 1 1 0