human
Write me a code to construct a Binary Tree from Postorder and Inorder and the other steps required given the following:
Construct a Binary Tree from Postorder and Inorder | Recursive function to construct binary of size n from Inorder traversal in [ ] and Postorder traversal post [ ] . Initial values of inStrt and inEnd should be 0 and n - 1. The function doesn 't do any error checking for cases where inorder and postorder do not form a tree.
Base case.
Pick current node from Postorder traversal using postIndex and decrement postIndex.
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 subtress.
This function mainly initializes index of root and calls buildUtil ( ).
Function to find index of value in arr [ start ... end ] . The function assumes that value is postsent in in [ ].
Helper function that allocates a new node.
This funtcion is here just to test.
Driver code"
How can the above be solved in Python?
assistant
#Here is code to construct a Binary Tree from Postorder and Inorder and the other steps required.
 def buildUtil ( In , post , inStrt , inEnd , pIndex ) :
	if ( inStrt > inEnd ) :
		return None
	node = newNode ( post [ pIndex [ 0 ] ] )
	pIndex [ 0 ] -= 1
	if ( inStrt == inEnd ) :
		return node
	iIndex = search ( In , inStrt , inEnd , node . data )
	node . right = buildUtil ( In , post , iIndex + 1 , inEnd , pIndex )
	node . left = buildUtil ( In , post , inStrt , iIndex - 1 , pIndex )
	return node
def buildTree ( In , post , n ) :
	pIndex = [ n - 1 ]
	return buildUtil ( In , post , 0 , n - 1 , pIndex )
def search ( arr , strt , end , value ) :
	i = 0
	for i in range ( strt , end + 1 ) :
		if ( arr [ i ] == value ) :
			break
	return i
class newNode :
	def __init__ ( self , data ) :
		self . data = data
		self . left = self . right = None
def preOrder ( node ) :
	if node == None :
		return
	print ( node . data , end = " ▁ " )
	preOrder ( node . left )
	preOrder ( node . right )
if __name__ == ' _ _ main _ _ ' :
	In = [ 4 , 8 , 2 , 5 , 1 , 6 , 3 , 7 ]
	post = [ 8 , 4 , 5 , 2 , 6 , 7 , 3 , 1 ]
	n = len ( In )
	root = buildTree ( In , post , n )
	print ( " Preorder ▁ of ▁ the ▁ constructed ▁ tree ▁ : " )
	preOrder ( root )