Given inorder and postorder traversals of a Binary Tree in the arrays in[] and post[] respectively. The task is to construct the binary tree from these traversals.
 
Example 1:
Input:
N = 8
in[] = 4 8 2 5 1 6 3 7
post[] =8 4 5 2 6 7 3 1
Output: 1 2 4 8 5 3 6 7
Explanation: For the given postorder and
inorder traversal of tree the  resultant
binary tree will be
           1
       /      \
     2         3
   /  \      /  \
  4    5    6    7
   \
     8
 
Example 2:
Input:
N = 5
in[] = 9 5 2 3 4
post[] = 5 9 3 4 2
Output: 2 9 5 4 3
Explanation:  
the  resultant binary tree will be
           2
        /     \
       9       4
        \     /
         5   3
 
Your Task:
You do not need to read input or print anything. Complete the function buildTree() which takes the inorder, postorder traversals and the number of nodes in the tree as input parameters and returns the root node of the newly constructed Binary Tree.
The generated output contains the preorder traversal of the constructed tree.
 
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{3}
1 <= in[i], post[i] <= 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3

'''
class Node:
            def __init__(self, data):
                self.data = data
                self.left = self.right = None
'''

#Function to return a tree created from postorder and inoreder traversals.
def buildTree(In, post, n):
    # your code here
    

Solutions:
class Node:

	def __init__(self, data):
		self.data = data
		self.left = self.right = None

def buildTree(In, post, n):
	mp = {}
	for i in range(n):
		if In[i] not in mp:
			mp[In[i]] = []
		mp[In[i]].append(i)
	postS = [n - 1]
	inS = 0
	inE = n - 1
	return solution(In, post, postS, inS, inE, mp)

def solution(inorder, postorder, postS, inS, inE, mp):
	if postS[0] < 0 or inS > inE:
		return None
	val = postorder[postS[0]]
	postS[0] -= 1
	root = Node(val)
	index = mp[val].pop(0)
	root.right = solution(inorder, postorder, postS, index + 1, inE, mp)
	root.left = solution(inorder, postorder, postS, inS, index - 1, mp)
	return root


def buildTree(In, post, n):
	poststart = instart = 0
	postend = inend = n - 1
	return constructTree(post, poststart, postend, In, instart, inend)

def search(In, instart, inend, val):
	for i in range(instart, inend + 1):
		if In[i] == val:
			return i

def constructTree(post, poststart, postend, In, instart, inend):
	if poststart > postend or instart > inend:
		return None
	root = Node(post[postend])
	elem = search(In, instart, inend, root.data)
	nelem = elem - instart
	root.left = constructTree(post, poststart, poststart + nelem - 1, In, instart, elem - 1)
	root.right = constructTree(post, poststart + nelem, postend - 1, In, elem + 1, inend)
	return root


def buildTree(In, post, n):
	if not In:
		return
	val = post.pop()
	root = Node(val)
	idx = In.index(val)
	root.right = buildTree(In[idx + 1:], post, n)
	root.left = buildTree(In[:idx], post, n)
	return root


def buildTree(inorder, postorder, n):

	def builder(inorder, postorder, in_start, in_end, post_start, post_end):
		if in_start > in_end or post_start > post_end:
			return None
		node = Node(postorder[post_end])
		for node_pos in range(in_start, in_end + 1):
			if inorder[node_pos] == postorder[post_end]:
				break
		left_total = node_pos - in_start - 1
		node.left = builder(inorder, postorder, in_start, node_pos - 1, post_start, post_start + left_total)
		node.right = builder(inorder, postorder, node_pos + 1, in_end, post_start + left_total + 1, post_end - 1)
		return node
	return builder(inorder, postorder, 0, n - 1, 0, n - 1)


def buildTree(In, post, n):
	if not In or not post:
		return
	index = In.index(post[-1])
	root = Node(post[-1])
	root.left = buildTree(In[0:index], post[0:index], n)
	root.right = buildTree(In[index + 1:], post[index:-1], n)
	return root


def buildTree(In, post, n):
	if In:
		index = In.index(post.pop())
		root = Node(In[index])
		root.right = buildTree(In[index + 1:], post, n)
		root.left = buildTree(In[:index], post, n)
		return root


def buildTree(In, post, n):
	global postindex
	postindex = n - 1

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

	def BuildTree_IPos(inOrder, postOrder, instart, inend):
		global postindex
		if instart > inend:
			return None
		tnode = Node(postOrder[postindex])
		postindex -= 1
		if instart == inend:
			return tnode
		inindex = SearchArray(inOrder, instart, inend, tnode.data)
		tnode.right = BuildTree_IPos(inOrder, postOrder, inindex + 1, inend)
		tnode.left = BuildTree_IPos(inOrder, postOrder, instart, inindex - 1)
		return tnode
	return BuildTree_IPos(In, post, 0, n - 1)


def _buildtree(postorder, poststart, postend, inorder, instart, inend, hashmap):
	if instart > inend or poststart > postend:
		return None
	root = Node(postorder[postend])
	inroot = hashmap[postorder[postend]]
	numsleft = inroot - instart
	root.left = _buildtree(postorder, poststart, poststart + numsleft - 1, inorder, instart, inroot - 1, hashmap)
	root.right = _buildtree(postorder, poststart + numsleft, postend - 1, inorder, inroot + 1, inend, hashmap)
	return root

def buildTree(inorder, postorder, n):
	if len(inorder) != len(postorder):
		return None
	hashmap = {}
	for (i, num) in enumerate(inorder):
		hashmap[num] = i
	return _buildtree(postorder, 0, n - 1, inorder, 0, n - 1, hashmap)


def buildTree(In, post, n):
	post_ind = [n - 1]

	def build(post=post, io=In, isi=0, iei=n - 1):
		if isi > iei:
			return None
		root = Node(post[post_ind[0]])
		post_ind[0] -= 1
		if isi == iei:
			return root
		for i in range(isi, iei + 1):
			if io[i] == root.data:
				break
		root.right = build(post, io, i + 1, iei)
		root.left = build(post, io, isi, i - 1)
		return root
	return build()


def buildTree(In, post, n):
	if not In or not post:
		return None
	idx = In.index(post[-1])
	root = Node(post.pop())
	root.right = buildTree(In[idx + 1:], post, n)
	root.left = buildTree(In[:idx], post, n)
	return root


def helper(inorder, postorder, indexS, indexE, mp):
	global postindex
	if indexS > indexE:
		return None
	root = Node(postorder[postindex])
	postindex -= 1
	index = mp[root.data]
	root.right = helper(inorder, postorder, index + 1, indexE, mp)
	root.left = helper(inorder, postorder, indexS, index - 1, mp)
	return root

def buildTree(inorder, postorder, n):
	global postindex
	postindex = n - 1
	mp = {}
	for i in range(n):
		mp[inorder[i]] = i
	return helper(inorder, postorder, 0, n - 1, mp)


def buildTree(inorder, postorder, n):
	lookup = dict()
	for (i, num) in enumerate(inorder):
		lookup[num] = i
	return buildTreeRecu(lookup, postorder, inorder, len(postorder), 0, len(inorder))

def buildTreeRecu(lookup, postorder, inorder, postEnd, inStart, inEnd):
	if inStart == inEnd:
		return None
	node = Node(postorder[postEnd - 1])
	i = lookup[postorder[postEnd - 1]]
	node.left = buildTreeRecu(lookup, postorder, inorder, postEnd - 1 - (inEnd - i - 1), inStart, i)
	node.right = buildTreeRecu(lookup, postorder, inorder, postEnd - 1, i + 1, inEnd)
	return node


def buildTree(inorder, postorder, n):
	postorder = postorder[::-1]

	def sol(post, ino):
		if not post and (not ino):
			return None
		mid_val = ino.index(post[0])
		root = Node(post[0])
		root.left = sol(post[len(post) - mid_val:], ino[:mid_val])
		root.right = sol(post[1:len(post) - mid_val], ino[mid_val + 1:])
		return root
	return sol(postorder, inorder)


def tree(In, post, start, end, n):
	global index
	if index < 0 or start > end:
		return None
	element = post[index]
	index -= 1
	root = Node(element)
	for pos in range(start, end + 1):
		if In[pos] == element:
			break
	root.right = tree(In, post, pos + 1, end, n)
	root.left = tree(In, post, start, pos - 1, n)
	return root

def buildTree(In, post, n):
	global index
	index = n - 1
	root = tree(In, post, 0, n - 1, n)
	return root


def tree(inn, post, strt, end, n):
	global ind
	if ind < 0 or strt > end:
		return
	root = Node(post[ind])
	for mid in range(strt, end + 1):
		if inn[mid] == post[ind]:
			break
	ind -= 1
	root.right = tree(inn, post, mid + 1, end, n)
	root.left = tree(inn, post, strt, mid - 1, n)
	return root

def buildTree(In, post, n):
	global ind
	ind = n - 1
	return tree(In, post, 0, n - 1, n)


def buildTree(In, post, n):
	return solve(In, post, 0, n - 1, n)

def solve(In, post, start, end, n):
	if n == 0:
		return None
	rootdata = post[n - 1]
	root = Node(rootdata)
	rootindexin = -1
	for i in range(start, end + 1):
		if In[i] == rootdata:
			rootindexin = i
			break
	if rootindexin == -1:
		return None
	leftorder = In[start:rootindexin]
	rightorder = In[rootindexin + 1:end + 1]
	lenleftsubtree = len(leftorder)
	leftpost = post[:lenleftsubtree]
	rightpost = post[lenleftsubtree:n - 1]
	leftchild = solve(In, leftpost, start, start + lenleftsubtree - 1, lenleftsubtree)
	rightchild = solve(In, rightpost, rootindexin + 1, end, n - 1 - lenleftsubtree)
	root.left = leftchild
	root.right = rightchild
	return root


def buildTree(inorder, postorder, n=None):
	if not inorder or not postorder:
		return
	rootval = postorder[-1]
	root = Node(rootval)
	rootidx = inorder.index(rootval)
	if n is None:
		n = len(inorder)
	leftsize = rootidx
	rightsize = n - rootidx - 1
	root.left = buildTree(inorder[:rootidx], postorder[:rootidx], leftsize)
	root.right = buildTree(inorder[rootidx + 1:], postorder[leftsize:leftsize + rightsize], rightsize)
	return root


def buildTree(In, post, n=None):
	if not In or not post:
		return None
	root_value = post[-1]
	root = Node(root_value)
	root_index = In.index(root_value)
	if n is None:
		n = len(In)
	leftsize = root_index
	rightsize = n - root_index - 1
	root.left = buildTree(In[:root_index], post[:root_index], leftsize)
	root.right = buildTree(In[root_index + 1:], post[leftsize:leftsize + rightsize], rightsize)
	return root


def find(inorder, post, instart, inend):
	if instart > inend:
		return
	root = Node(post[find.postindex])
	find.postindex -= 1
	for i in range(instart, inend + 1):
		if inorder[i] == root.data:
			break
	root.right = find(inorder, post, i + 1, inend)
	root.left = find(inorder, post, instart, i - 1)
	return root

def buildTree(inorder, post, n):
	find.postindex = n - 1
	return find(inorder, post, 0, n - 1)


def buildTree(In, post, n):
	if not In or not post:
		return
	root_val = post[-1]
	root = Node(root_val)
	root_index = In.index(root_val)
	if n == None:
		n = len(In)
	left_size = root_index
	right_size = n - root_index - 1
	root.left = buildTree(In[:root_index], post[:root_index], left_size)
	root.right = buildTree(In[root_index + 1:], post[left_size:left_size + right_size], right_size)
	return root


def buildTree(In, post, n):
	global index

	def findPosition(element, In):
		for i in range(len(In)):
			if In[i] == element:
				return i

	def rec(In, post):
		global index
		if len(In) == 0:
			return None
		elem = post[index]
		index -= 1
		root = Node(elem)
		pos = findPosition(elem, In)
		root.right = rec(In[pos + 1:], post)
		root.left = rec(In[:pos], post)
		return root
	index = n - 1
	return rec(In, post)


def build(In, s1, e1, post, s2, e2):
	if s1 > e1:
		return None
	node = Node(post[e2])
	idx = In.index(post[e2])
	node.left = build(In, s1, idx - 1, post, s2, idx - 1 - s1 + s2)
	node.right = build(In, idx + 1, e1, post, e2 - e1 + idx, e2 - 1)
	return node

def buildTree(In, post, n):
	return build(In, 0, n - 1, post, 0, n - 1)


def buildTree(inorder, postorder, n):
	if inorder == None or len(inorder) != len(postorder):
		return None
	a = {}
	for i in range(len(inorder)):
		a[inorder[i]] = i

		def createTree(inorder, ip, ie, postorder, pp, pe, a):
			root = Node(postorder[pe])
			if pp > pe or ip > ie:
				return None
			inRoot = a[postorder[pe]]
			numsLeft = inRoot - ip
			root.left = createTree(inorder, ip, inRoot - 1, postorder, pp, pp + numsLeft - 1, a)
			root.right = createTree(inorder, inRoot + 1, ie, postorder, pp + numsLeft, pe - 1, a)
			return root
	return createTree(inorder, 0, len(inorder) - 1, postorder, 0, len(postorder) - 1, a)


def buildTree(In, post, n):
	if not In or not post:
		return None
	root = Node(post[n - 1])
	index = In.index(post[n - 1])
	root.left = buildTree(In[:index], post[:index], len(post[:index]))
	root.right = buildTree(In[index + 1:], post[index:n - 1], len(post[index:n - 1]))
	return root


pind = 0

def buildTree(inorder, postorder, n=8):
	if not inorder or not postorder:
		return None
	root_val = postorder[-1]
	root = Node(root_val)
	idx = inorder.index(root_val)
	root.left = buildTree(inorder[:idx], postorder[:idx])
	root.right = buildTree(inorder[idx + 1:], postorder[idx:-1])
	return root


def buildTree(In, post, n):
	if not In:
		return None
	root = Node(post.pop())
	inx = In.index(root.data)
	root.right = buildTree(In[inx + 1:], post, n)
	root.left = buildTree(In[:inx], post, n)
	return root


def buildTree(In, post, n):
	inorderidx = {v: i for (i, v) in enumerate(In)}

	def helper(l, r):
		if l > r:
			return None
		root = Node(post.pop())
		idx = inorderidx[root.data]
		root.right = helper(idx + 1, r)
		root.left = helper(l, idx - 1)
		return root
	return helper(0, len(In) - 1)


def build(inorder, postorder, start_in, end_in, start_post, end_post, dic):
	if start_post > end_post or start_in > end_in:
		return None
	root = Node(postorder[end_post])
	index_root = [x for x in dic[root.data] if start_in <= x <= end_in]
	num_left = index_root[0] - start_in
	root.left = build(inorder, postorder, start_in, index_root[0] - 1, start_post, start_post + num_left - 1, dic)
	root.right = build(inorder, postorder, index_root[0] + 1, end_in, start_post + num_left, end_post - 1, dic)
	return root

def buildTree(inorder, postorder, n):
	dic = {}
	for i in range(n):
		if inorder[i] in dic:
			dic[inorder[i]].append(i)
		else:
			dic[inorder[i]] = [i]
	return build(inorder, postorder, 0, n - 1, 0, n - 1, dic)


def buildTree(In, post, n):
	d = {}
	for i in range(n):
		if In[i] in d:
			d[In[i]].append(i)
		else:
			d[In[i]] = [i]

	def helper(inorder, postorder, li, ri, lp, rp):
		if li > ri or lp > rp:
			return None
		root = Node(postorder[rp])
		indices = d[postorder[rp]]
		for i in indices:
			if li <= i <= ri:
				index = i
				break
		(rightSize, leftSize) = (ri - index, index - li)
		root.left = helper(inorder, postorder, li, index - 1, lp, lp + leftSize - 1)
		root.right = helper(inorder, postorder, index + 1, ri, lp + leftSize, rp - 1)
		return root
	return helper(In, post, 0, n - 1, 0, n - 1)


def Search(start, end, value, inorder):
	for indx in range(start, end + 1):
		if value == inorder[indx]:
			return indx
	return -1

def BuildTree(In, post, postindx, instart, inend):
	if instart > inend:
		return None
	if postindx[0] < 0:
		return None
	root = Node(post[postindx[0]])
	inindx = Search(instart, inend, post[postindx[0]], In)
	postindx[0] -= 1
	root.right = BuildTree(In, post, postindx, inindx + 1, inend)
	root.left = BuildTree(In, post, postindx, instart, inindx - 1)
	return root

def buildTree(In, post, n):
	postindx = [n - 1]
	return BuildTree(In, post, postindx, 0, n - 1)


def buildTree(In, post, n):

	def dum(In, post):
		if not In:
			return None
		p = post.pop()
		root = Node(p)
		i = In.index(p)
		root.right = dum(In[i + 1:], post)
		root.left = dum(In[:i], post)
		return root
	return dum(In, post)


def buildTree(In, post, n):
	if not In:
		return None
	root_val = post.pop()
	root = Node(root_val)
	in_order_index = In.index(root_val)
	root.right = buildTree(In[in_order_index + 1:], post, n)
	root.left = buildTree(In[:in_order_index], post, n)
	return root


def buildTree(inorder, postorder, n):
	if not inorder or not postorder:
		return None
	root_val = postorder.pop()
	root = Node(root_val)
	inorder_index = inorder.index(root_val)
	root.right = buildTree(inorder[inorder_index + 1:], postorder, n)
	root.left = buildTree(inorder[:inorder_index], postorder, n)
	return root


def buildTree(In, post, n):

	def buildTre(In, post):
		if len(In) == 0:
			return None
		root = Node(post.pop())
		ids = In.index(root.data)
		root.right = buildTre(In[ids + 1:], post)
		root.left = buildTre(In[:ids], post)
		return root
	return buildTre(In, post)


def buildTree(inorder, postorder, n):
	if inorder == [] or postorder == []:
		return
	root = Node(postorder[-1])
	index = inorder.index(postorder[-1])
	root.left = buildTree(inorder[0:index], postorder[0:index], n)
	root.right = buildTree(inorder[index + 1:len(inorder)], postorder[index:len(inorder) - 1], n)
	return root


def buildTree(ino, post, n):
	if not ino or not post:
		return None
	val = post.pop()
	mid = ino.index(val)
	root = Node(val)
	root.right = buildTree(ino[mid + 1:], post, n)
	root.left = buildTree(ino[:mid], post, n)
	return root


def buildTree(io, po, n):
	if len(io) != len(po):
		return None

	def util(d, io, io1, io2, po, po1, po2):
		if io1 > io2 or po1 > po2:
			return None
		root = Node(po[po2])
		ind = d[po[po2]]
		if io1 != io2:
			root.left = util(d, io, io1, ind - 1, po, po1, po1 + ind - io1 - 1)
			root.right = util(d, io, ind + 1, io2, po, po1 + ind - io1, po2 - 1)
		return root
	n = len(io)
	d = {}
	for i in range(n):
		d[io[i]] = i
	return util(d, io, 0, n - 1, po, 0, n - 1)


from collections import defaultdict

def buildTree(In, post, n):
	if len(In) != len(post):
		return None
	instart = 0
	inend = len(In) - 1
	poststart = 0
	postend = len(post) - 1
	hmap = defaultdict(int)
	for i in range(0, len(In)):
		hmap[In[i]] = i
	return helper(post, poststart, postend, In, instart, inend, hmap)

def helper(postorder, poststart, postend, inorder, instart, inend, hmap):
	if poststart > postend or instart > inend:
		return None
	root = Node(postorder[postend])
	inmid = hmap[root.data]
	remaining = inmid - instart
	root.left = helper(postorder, poststart, poststart + remaining - 1, inorder, instart, inmid - 1, hmap)
	root.right = helper(postorder, poststart + remaining, postend - 1, inorder, inmid + 1, inend, hmap)
	return root


mp = {}

def buildTreeUtil(In, post, instart, inend, preIndex):
	if instart > inend:
		return None
	new = Node(post[preIndex[0]])
	preIndex[0] -= 1
	if instart == inend:
		return new
	inIndex = mp[new.data]
	new.right = buildTreeUtil(In, post, inIndex + 1, inend, preIndex)
	new.left = buildTreeUtil(In, post, instart, inIndex - 1, preIndex)
	return new

def buildTree(In, post, n):
	global mp
	for i in range(n):
		mp[In[i]] = i
	preIndex = [n - 1]
	return buildTreeUtil(In, post, 0, n - 1, preIndex)


def buildTree(inorder, post, n):
	inmap = {}
	for (i, n) in enumerate(inorder):
		if inmap.get(n, False):
			inmap[n].append(i)
		else:
			inmap[n] = [i]
	return Util(inorder, 0, len(inorder) - 1, post, 0, len(inorder) - 1, inmap)

def findInRoot(num, inmap, offset):
	val = inmap[num]
	if len(val) > 0:
		for each in val:
			if each >= offset:
				return each
	return val[0]

def Util(inorder, instart, inend, post, pstart, pend, inmap):
	if instart > inend or pstart > pend:
		return None
	num = post[pend]
	inroot = findInRoot(num, inmap, instart)
	numsleft = inroot - instart
	node = Node(num)
	node.left = Util(inorder, instart, inroot - 1, post, pstart, pstart + numsleft - 1, inmap)
	node.right = Util(inorder, inroot + 1, inend, post, pstart + numsleft, pend - 1, inmap)
	return node


def buildTree(In, post, n):
	inorderMap = {}
	for (i, e) in enumerate(In):
		inorderMap[e] = i
	i = n - 1

	def buildTreeUtil(l, r):
		nonlocal i, inorderMap
		if l >= r:
			return None
		else:
			n = Node(post[i])
			i -= 1
			n.right = buildTreeUtil(inorderMap[n.data] + 1, r)
			n.left = buildTreeUtil(l, inorderMap[n.data])
		return n
	return buildTreeUtil(0, n)


def solve(In, post, post_idx, in_start_idx, in_end_idx, node_map):
	if post_idx[0] < 0 or in_start_idx > in_end_idx:
		return None
	element = post[post_idx[0]]
	root = Node(element)
	post_idx[0] -= 1
	pos = node_map[element]
	root.right = solve(In, post, post_idx, pos + 1, in_end_idx, node_map)
	root.left = solve(In, post, post_idx, in_start_idx, pos - 1, node_map)
	return root

def buildTree(In, post, n):
	node_map = {}
	for (i, x) in enumerate(In):
		node_map[x] = i
	post_idx = [n - 1]
	(in_start_idx, in_end_idx) = (0, n - 1)
	root = solve(In, post, post_idx, in_start_idx, in_end_idx, node_map)
	return root


def buildTree(In, post, n):
	if n <= 0:
		return None
	root = Node(post[n - 1])
	for i in range(n):
		if In[i] == post[n - 1]:
			break
	root.left = buildTree(In, post, i)
	root.right = buildTree(In[i + 1:], post[i:], n - i - 1)
	return root


def buildTree(In, post, n):
	if n == 0:
		return
	pos = In.index(post[-1])
	node = Node(post[-1])
	node.left = buildTree(In[:pos], post[:pos], pos)
	node.right = buildTree(In[pos + 1:], post[pos:n - 1], n - 1 - pos)
	return node


def buildTree(In, post, n):
	if not In and (not post):
		return None
	n = len(post) - 1
	root = Node(post[n])
	mid = In.index(post[n])
	root.left = buildTree(In[:mid], post[:mid], n)
	root.right = buildTree(In[mid + 1:], post[mid:n], n)
	return root


def buildTree(In, post, n):

	def recursive(In, post, idx=n - 1, lo=0, hi=n - 1):
		if idx < 0:
			return (None, idx)
		cur = post[idx]
		root = None
		for i in range(lo, hi + 1):
			if In[i] == cur:
				root = Node(cur)
				break
		if root:
			(root.right, idx) = recursive(In, post, idx - 1, i + 1, hi)
			(root.left, idx) = recursive(In, post, idx, lo, i - 1)
		return (root, idx)
	(root, idx) = recursive(In, post)
	return root


def buildUtil(In, post, inStrt, inEnd, pIndex):
	if inStrt > inEnd:
		return None
	node = Node(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


def buildTree(In, post, n):

	def buildtree(ino, ist, ied, pos, pst, ped, mp):
		if ist > ied or pst > ped:
			return None
		root = Node(pos[ped])
		inroot = mp[root.data]
		numsleft = inroot - ist
		root.left = buildtree(ino, ist, inroot - 1, pos, pst, pst + numsleft - 1, mp)
		root.right = buildtree(ino, inroot + 1, ied, pos, pst + numsleft, ped - 1, mp)
		return root

	def build(ino, pos, n):
		mp = {}
		for i in range(n):
			mp[ino[i]] = mp.get(ino[i], 0)
			mp[ino[i]] = i
		root = buildtree(ino, 0, n - 1, pos, 0, n - 1, mp)
		return root
	return build(In, post, n)


postIndex = -1

def helper(d, post, l, r):
	global postIndex
	if l > r:
		return None
	x = post[postIndex]
	postIndex -= 1
	index = d[x]
	node = Node(x)
	if l == r:
		return node
	node.right = helper(d, post, index + 1, r)
	node.left = helper(d, post, l, index - 1)
	return node

def buildTree(In, post, n):
	global postIndex
	postIndex = n - 1
	d = dict()
	for i in range(n):
		d[In[i]] = i
	return helper(d, post, 0, n - 1)


def buildTree(inorder, postorder, n):
	inomap = {}
	for (i, el) in enumerate(inorder):
		inomap[el] = i

	def get_tree(isi, iei, ppsi, ppei):
		if ppei < ppsi:
			return None
		inidx = inomap[postorder[ppei]]
		l = inidx - isi
		root = Node(postorder[ppei])
		if ppsi == ppei:
			return root
		root.left = get_tree(isi, inidx - 1, ppsi, ppsi + l - 1)
		root.right = get_tree(inidx + 1, iei, ppsi + l, ppei - 1)
		return root
	return get_tree(0, len(inorder) - 1, 0, len(postorder) - 1)


def build(ino, post, h, ind, i, j):
	if i > j:
		return None
	root = Node(post[ind[0]])
	ind[0] -= 1
	if i == j:
		return root
	root.right = build(ino, post, h, ind, h[root.data] + 1, j)
	root.left = build(ino, post, h, ind, i, h[root.data] - 1)
	return root

def buildTree(ino, post, n):
	posind = n - 1
	h = {}
	for i in range(len(ino)):
		h[ino[i]] = i
	return build(ino, post, h, [posind], 0, n - 1)


def positioner(In, start, end, element):
	i = start
	while i <= end:
		if In[i] == element:
			return i
		i += 1

def treeBuilder(In, post, n, index, start, end):
	if index[0] < 0 or start > end:
		return None
	element = post[index[0]]
	index[0] = index[0] - 1
	root = Node(element)
	position = positioner(In, start, end, element)
	root.right = treeBuilder(In, post, n, index, position + 1, end)
	root.left = treeBuilder(In, post, n, index, start, position - 1)
	return root

def buildTree(In, post, n):
	start = 0
	end = n - 1
	index = [n - 1]
	ans = treeBuilder(In, post, n, index, start, end)
	return ans


def buildTree(In, post, n):
	post_idx = [n - 1]
	return buildUtil(In, 0, n - 1, post, post_idx)

def buildUtil(inorder, start, end, postorder, post_idx):
	if start > end:
		return None
	i = post_idx[0]
	root = postorder[i]
	post_idx[0] -= 1
	for idx in range(start, end + 1):
		if inorder[idx] == root:
			break
	n = Node(root)
	n.right = buildUtil(inorder, idx + 1, end, postorder, post_idx)
	n.left = buildUtil(inorder, start, idx - 1, postorder, post_idx)
	return n


def buildTree(In, post, n):
	root = post[-1]
	rootNode = Node(root)
	rootIndex = In.index(root)
	if In[0:rootIndex]:
		rootNode.left = buildTree(In[0:rootIndex], post[0:rootIndex], rootIndex)
	if In[rootIndex + 1:]:
		rootNode.right = buildTree(In[rootIndex + 1:], post[rootIndex:n - 1], n - 1 - rootIndex)
	return rootNode


from collections import OrderedDict

def buildTree(In, post, n):
	g = OrderedDict()
	for i in range(0, n):
		c = In[i]
		g[c] = i
	ps = 0
	iss = 0
	pe = n - 1
	ie = n - 1
	t = ans(In, post, ps, pe, iss, ie, g)
	return t

def ans(In, post, ps, pe, iss, ie, g):
	if ps > pe or iss > ie:
		return None
	else:
		root = Node(post[pe])
		r = g[post[pe]]
		left = r - iss
		root.left = ans(In, post, ps, ps + left - 1, iss, r - 1, g)
		root.right = ans(In, post, ps + left, pe - 1, r + 1, ie, g)
		return root


def buildTree(inorder, postorder, n):
	if not inorder or not postorder:
		return None
	root = Node(postorder[n - 1])
	mid = inorder.index(postorder[n - 1])
	root.left = buildTree(inorder[:mid], postorder[:mid], mid)
	root.right = buildTree(inorder[mid + 1:], postorder[mid:n - 1], n - 1 - mid)
	return root


def buildTree(In, post, n):
	i = [n - 1]
	mydict = {}
	for j in range(n):
		mydict[In[j]] = j

	def construct(start, end):
		if start > end:
			return None
		root = Node(post[i[0]])
		i[0] -= 1
		if start == end:
			return root
		middle = mydict[root.data]
		root.right = construct(middle + 1, end)
		root.left = construct(start, middle - 1)
		return root
	return construct(0, n - 1)


mp = {}

def buildTree(In, post, n):
	global post_ind, mp
	post_ind = len(post) - 1

	def recur(In, post, isi, iei):
		if isi > iei:
			return None
		global post_ind, mp
		curr = post[post_ind]
		root = Node(curr)
		post_ind -= 1
		if isi == iei:
			return root
		i = mp[curr]
		root.right = recur(In, post, i + 1, iei)
		root.left = recur(In, post, isi, i - 1)
		return root
	for i in range(len(In)):
		mp[In[i]] = i
	return recur(In, post, 0, len(In) - 1)


def buildTree(ino, post, n):
	if not ino or not post:
		return None
	root = Node(post[-1])
	m = post.index(root.data)
	k = ino.index(root.data)
	root.left = buildTree(ino[:k], post[:k], n)
	root.right = buildTree(ino[k + 1:], post[k:m], n)
	return root


def buildTree(In, post, n):

	def builder(pi, pj, l, r):
		if pj < pi:
			return None
		root = Node(post[pj])
		i = l
		while i <= r:
			if root.data == In[i]:
				break
			i += 1
		root.right = builder(pj - (r - i), pj - 1, i + 1, r)
		root.left = builder(pi, pj - (r - i) - 1, l, i - 1)
		return root
	return builder(0, len(post) - 1, 0, len(In) - 1)


def buildTree(In, post, n):
	global preOrderIndex
	preOrderIndex = n - 1

	def solve(In, post, inorderStart, inorderEnd):
		global preOrderIndex
		if preOrderIndex < 0 or inorderStart > inorderEnd:
			return None
		root = Node(post[preOrderIndex])
		preOrderIndex -= 1
		for i in range(inorderStart, inorderEnd + 1):
			if In[i] == root.data:
				break
		root.right = solve(In, post, i + 1, inorderEnd)
		root.left = solve(In, post, inorderStart, i - 1)
		return root
	n = len(In)
	ans = solve(In, post, 0, n - 1)
	return ans


def buildTree(In, post, n):
	i = n - 1
	j = n - 1
	root = Node('a')
	st = []
	st.append(root)
	cur = root
	while i >= 0:
		if st[-1].data != In[j]:
			if st[-1].data == cur.data:
				cur.right = Node(post[i])
				cur = cur.right
			else:
				cur.left = Node(post[i])
				cur = cur.left
			i -= 1
			st.append(cur)
		else:
			j -= 1
			cur = st.pop()
	return root.right


def buildTree(inorder, postorder, n):
	inMap = {}
	import sys
	sys.setrecursionlimit(1000000)
	for (i, num) in enumerate(inorder):
		if inMap.get(num, sys.maxsize) == sys.maxsize:
			inMap[num] = [i]
		else:
			inMap[num].append(i)
	return buildTreeUtil(inorder, 0, len(inorder) - 1, postorder, 0, len(postorder) - 1, inMap)

def buildTreeUtil(inorder, inStart, inEnd, postorder, postStart, postEnd, inMap):
	if inStart > inEnd or postStart > postEnd:
		return None
	num = postorder[postEnd]
	node = Node(num)
	inRoot = findInRoot(num, inStart, inMap)
	numsLeft = inRoot - inStart
	node.left = buildTreeUtil(inorder, inStart, inRoot - 1, postorder, postStart, postStart + numsLeft - 1, inMap)
	node.right = buildTreeUtil(inorder, inRoot + 1, inEnd, postorder, postStart + numsLeft, postEnd - 1, inMap)
	return node

def findInRoot(num, inStart, inMap):
	inFind = inMap[num]
	if len(inFind) == 1:
		return inFind[0]
	else:
		for each in inFind:
			if each >= inStart:
				return each


def buildTree(In, post, n):
	if not In or not post:
		return None
	value = post[-1]
	root = Node(value)
	mid = In.index(value)
	root.left = buildTree(In[:mid], post[:mid], n)
	root.right = buildTree(In[mid + 1:], post[mid:-1], n)
	return root


def buildTree(In, post, n):
	return helper(0, n - 1, post, In, n - 1)[0]

def helper(start, stop, post, In, p):
	if p < 0:
		return (None, -1)
	if start > stop:
		return (None, p)
	for i in range(start, stop + 1):
		if post[p] == In[i]:
			(right, p) = helper(i + 1, stop, post, In, p - 1)
			(left, p) = helper(start, i - 1, post, In, p)
			tree = Node(In[i])
			tree.left = left
			tree.right = right
			return (tree, p)
	return None