Construct Tree from given Inorder and Preorder traversals | A binary tree node ; 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  ; Pich current node from Preorder traversal using preIndex and increment preIndex ; If this node has no children then return ; Else find the index of this node in Inorder traversal ; Using index in Inorder Traversal , construct left and right subtrees ; Function to find index of value in arr [ start ... end ] The function assumes that value is rpesent in inOrder [ ] ; This funtcion is here just to test buildTree ( ) ; first recur on left child ; then print the data of node ; now recur on right child ; Driver program to test above function ; Let us test the build tree by priting Inorder traversal
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def buildTree ( inOrder , preOrder , inStrt , inEnd ) : NEW_LINE INDENT if ( inStrt > inEnd ) : NEW_LINE INDENT return None NEW_LINE DEDENT tNode = Node ( preOrder [ buildTree . preIndex ] ) NEW_LINE buildTree . preIndex += 1 NEW_LINE if inStrt == inEnd : NEW_LINE INDENT return tNode NEW_LINE DEDENT inIndex = search ( inOrder , inStrt , inEnd , tNode . data ) NEW_LINE tNode . left = buildTree ( inOrder , preOrder , inStrt , inIndex - 1 ) NEW_LINE tNode . right = buildTree ( inOrder , preOrder , inIndex + 1 , inEnd ) NEW_LINE return tNode NEW_LINE DEDENT def search ( arr , start , end , value ) : NEW_LINE INDENT for i in range ( start , end + 1 ) : NEW_LINE INDENT if arr [ i ] == value : NEW_LINE INDENT return i NEW_LINE DEDENT DEDENT DEDENT def printInorder ( node ) : NEW_LINE INDENT if node is None : NEW_LINE INDENT return NEW_LINE DEDENT printInorder ( node . left ) NEW_LINE print node . data , NEW_LINE printInorder ( node . right ) NEW_LINE DEDENT inOrder = [ ' D ' , ' B ' , ' E ' , ' A ' , ' F ' , ' C ' ] NEW_LINE preOrder = [ ' A ' , ' B ' , ' D ' , ' E ' , ' C ' , ' F ' ] NEW_LINE buildTree . preIndex = 0 NEW_LINE root = buildTree ( inOrder , preOrder , 0 , len ( inOrder ) - 1 ) NEW_LINE print " Inorder ▁ traversal ▁ of ▁ the ▁ constructed ▁ tree ▁ is " NEW_LINE printInorder ( root ) NEW_LINE