Python with Tree Traversal

# Python program to construct tree using inorder and
# preorder traversals

Depth First Traversals:
(a) Inorder(Left, Root, Right):
    4 2 5 1 3
(b) Preorder(Root, Left, Right):
    1 2 4 5 3
(c) Postorder(Left, Right, Root):
    4 5 2 3 1

Breadth First or Level Order Traversal:
    1 2 3 4 5
# A binary tree node


class Node:

    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

"""Recursive function to construct binary of size len from
   Inorder traversal in[] and Preorder traversal pre[].  Initial values
   of inStrt and inEnd should be 0 and len -1.  The function doesn't
   do any error checking for cases where inorder and preorder
   do not form a tree """


def buildTree(inOrder, preOrder, inStrt, inEnd):

    if (inStrt > inEnd):
        return None

    # Pich current node from Preorder traversal using
    # preIndex and increment preIndex
    tNode = Node(preOrder[buildTree.preIndex])
    buildTree.preIndex += 1

    # If this node has no children then return
    if inStrt == inEnd:
        return tNode

    # Else find the index of this node in Inorder traversal
    inIndex = search(inOrder, inStrt, inEnd, tNode.data)

    # Using index in Inorder Traversal, construct left
    # and right subtrees
    tNode.left = buildTree(inOrder, preOrder, inStrt, inIndex - 1)
    tNode.right = buildTree(inOrder, preOrder, inIndex + 1, inEnd)

    return tNode

# UTILITY FUNCTIONS
# Function to find index of vaue in arr[start...end]
# The function assumes that value is rpesent in inOrder[]


def search(arr, start, end, value):
    for i in range(start, end + 1):
        if arr[i] == value:
            return i


def printInorder(node):
    if node is None:
        return

    # first recur on left child
    printInorder(node.left)

    # then print the data of node
    print node.data,

    # now recur on right child
    printInorder(node.right)


def printPostorder(node):
    if node is None:
        return

    # first recur on left child
    printPostorder(node.left)

    # now recur on right child
    printPostorder(node.right)

    # then print the data of node
    print node.data,


# Driver program to test above function
# inOrder = [4, 2, 5, 1, 3, 6]
# preOrder = [1, 2, 4, 5, 3, 6]
# postOrder = [4, 5, 2, 6, 3, 1]

inOrder = ['D', 'B', 'E', 'A', 'F', 'C']
preOrder = ['A', 'B', 'D', 'E', 'C', 'F']
postOrder = ['D', 'E', 'B', 'F', 'C', 'A']

# Static variable preIndex
buildTree.preIndex = 0
root = buildTree(inOrder, preOrder, 0, len(inOrder) - 1)

# Let us test the build tree by priting Inorder traversal
print "Inorder traversal of the constructed tree is"
printInorder(root)
print "\nPostorder traversal of the constructed tree is"
printPostorder(root)