Given a postfix expression. Your task is to complete the method constructTree(). The output of the program will print the infix expression of the given postfix expression.
Input:
The constructTree() function takes a single argument as input, character array containing the given postfix expression.
Output:
Infix expression should be printed for each given postfix expression.
Constraints:
1<=T<=50
1<=length_of_expression<=40
Example:
Input:
2
ab+ef*g*-
wlrb+-*
Output:
a + b - e * f * g
w * l - r + b
Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

Difficulty: MEDIUM
Tags: Tree algorithms

Data structures
Skill types: Data structures

Starter code:
#User function Template for python3



def constructTree(postfix):

    #your code goes here

Solutions:
def is_operator(i):
	return i in ['*', '^', '/', '+', '-']

def constructTree(postfix):
	stack = []
	for i in postfix:
		if not is_operator(i):
			q = et(i + ' ')
			stack.append(q)
		else:
			right_child = stack.pop()
			left_child = stack.pop()
			q = et(i + ' ')
			q.left = left_child
			q.right = right_child
			stack.append(q)
	return stack.pop()


def constructTree(postfix):
	curr = [len(postfix) - 1]
	arr = []
	for i in postfix:
		arr.append(i)
	root = toexpressiontree(arr, curr)
	return root

def toexpressiontree(postfix, curr):
	if curr[0] < 0:
		return None
	data = postfix[curr[0]] + ' '
	node = et(data)
	temp = curr[0]
	curr[0] = curr[0] - 1
	if isOperator(postfix[temp]):
		node.right = toexpressiontree(postfix, curr)
		node.left = toexpressiontree(postfix, curr)
	return node


def inor(root):
	if root:
		inor(root.left)
		print(root.value, end=' ')
		inor(root.right)

def constructTree(postfix):
	s = []
	for c in postfix:
		if not isOperator(c):
			s.append(et(c))
		else:
			op2 = s.pop()
			op1 = s.pop()
			node = et(c)
			node.left = op1
			node.right = op2
			s.append(node)
	inor(s[-1])
	return None


def Construct(postfix, postindx):
	if postindx[0] < 0:
		return None
	if isOperator(postfix[postindx[0]]) == False:
		temp = et(postfix[postindx[0]] + ' ')
		postindx[0] -= 1
		return temp
	root = et(postfix[postindx[0]] + ' ')
	postindx[0] -= 1
	root.right = Construct(postfix, postindx)
	root.left = Construct(postfix, postindx)
	return root

def constructTree(postfix):
	postindx = [len(postfix) - 1]
	root = Construct(postfix, postindx)
	return root


from math import log

def constructTree(postfix):
	digits = []
	for item in postfix:
		if item.isalpha():
			digits.append(item)
		else:
			item2 = digits.pop()
			item1 = digits.pop()
			digits.append(item1 + item + item2)
	start = et(0)
	stack = [(start, digits[0])]
	while stack:
		(root, path) = stack.pop()
		if len(path) == 1:
			root.value = path + ' '
			continue
		n = 2 ** int(log(len(path) + 1, 2) - 1) - 1
		root.value = path[n] + ' '
		root.left = et(0)
		root.right = et(0)
		stack.append((root.left, path[:n]))
		stack.append((root.right, path[n + 1:]))
	return start


def constructTree(postfix):
	stack = []
	for char in postfix:
		temp = et(char + ' ')
		if char.isalnum():
			stack.append(temp)
		else:
			op2 = stack.pop(-1)
			op1 = stack.pop(-1)
			temp.right = op2
			temp.left = op1
			stack.append(temp)
	return stack.pop(-1)


def constructTree(postfix):
	stack = []
	for i in postfix:
		if i.isalpha():
			stack.append(et(i))
		else:
			e2 = stack.pop()
			e1 = stack.pop()
			exp = ' ' + i + ' '
			root = et(exp)
			root.left = e1
			root.right = e2
			stack.append(root)
	return stack[0]


class Node:

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

def iterativeStackSol(expression):
	stack = []
	for i in expression:
		if i.isalnum():
			stack.append(Node(i + ' '))
		else:
			node = Node(i + ' ')
			node.right = stack.pop(-1)
			node.left = stack.pop(-1)
			stack.append(node)
	return stack[0]

def buildtree(notation, index):
	if index[0] < 0:
		return None
	root = Node(notation[index[0]] + ' ')
	index[0] = index[0] - 1
	if not notation[index[0] + 1].isalnum():
		root.right = buildtree(notation, index)
		root.left = buildtree(notation, index)
	return root

def constructTree(postfix):
	return iterativeStackSol(postfix)


class Node:

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

def buildtree(notation, index):
	if index[0] < 0:
		return None
	root = Node(notation[index[0]] + ' ')
	index[0] = index[0] - 1
	if not notation[index[0] + 1].isalnum():
		root.right = buildtree(notation, index)
		root.left = buildtree(notation, index)
	return root

def constructTree(postfix):
	index = [len(postfix) - 1]
	return buildtree(postfix, index)


def constructTree(postfix):
	current = [len(postfix) - 1]
	arr = [i for i in postfix]
	return toexpressiontree(arr, current)

def toexpressiontree(postfix, current):
	if current[0] < 0:
		return None
	node = et(postfix[current[0]] + ' ')
	temp = current[0]
	current[0] = current[0] - 1
	if isOperator(postfix[temp]):
		(node.right, node.left) = (toexpressiontree(postfix, current), toexpressiontree(postfix, current))
	return node


def constructTree(postfix):
	if not postfix:
		return None
	s = []
	for e in postfix:
		if e.isalpha():
			s.append(et(e + ' '))
		elif isOperator(e):
			op = et(e + ' ')
			op.right = s.pop()
			op.left = s.pop()
			s.append(op)
	return s[0]


def constructTree(postfix):
	n = len(postfix)
	index = [n - 1]
	return construct_tree(postfix, index)

def construct_tree(postfix, curr):
	if curr[0] < 0:
		return None
	ch = postfix[curr[0]]
	node = et(ch + ' ')
	if isOperator(ch):
		curr[0] -= 1
		node.right = construct_tree(postfix, curr)
		curr[0] -= 1
		node.left = construct_tree(postfix, curr)
	return node


def constructTree(postfix):
	s = []
	for i in postfix:
		if isOperator(i):
			d = s.pop()
			e = s.pop()
			s.append(e + ' ' + i + ' ' + d)
		else:
			s.append(i)
	return et(s[0])


class Node:

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

def constructTree(postfix):
	arr = []
	for i in postfix:
		newNode = Node(i + ' ')
		if i.isalpha():
			arr.append(newNode)
		else:
			oper1 = arr.pop()
			oper2 = arr.pop()
			newNode.left = oper2
			newNode.right = oper1
			arr.append(newNode)
	return arr[0]


def constructTree(postfix):
	stack = []
	for ch in postfix:
		if ch.isalpha():
			stack.append(et(ch + ' '))
		else:
			a = stack.pop()
			b = stack.pop()
			node = et(ch + ' ')
			node.left = b
			node.right = a
			stack.append(node)
	return stack[0]

class et:

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

def isOperator(c):
	if c == '+' or c == '-' or c == '*' or (c == '/') or (c == '^'):
		return True
	return False

def inorder(t):
	if t:
		inorder(t.left)
		print(t.value, end='')
		inorder(t.right)
for _ in range(int(input())):
	postfix = input()
	r = constructTree(postfix)
	inorder(r)
	print()


def constructTree(postfix):

	def toexpressiontree(postfix, current):
		if current[0] < 0:
			return None
		data = postfix[current[0]] + ' '
		node = et(data)
		temp = current[0]
		current[0] = current[0] - 1
		if isOperator(postfix[temp]):
			node.right = toexpressiontree(postfix, current)
			node.left = toexpressiontree(postfix, current)
		return node
	current = [len(postfix) - 1]
	return toexpressiontree(postfix, current)

class et:

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

def isOperator(c):
	if c == '+' or c == '-' or c == '*' or (c == '/') or (c == '^'):
		return True
	return False

def inorder(t):
	if t:
		inorder(t.left)
		print(t.value, end='')
		inorder(t.right)
for _ in range(int(input())):
	postfix = input()
	r = constructTree(postfix)
	inorder(r)
	print()


def constructTree(postfix):
	st = {'-', '+', '*', '/', '^'}
	ans = []
	for i in postfix:
		if i in st:
			root = et(i + ' ')
			root.right = ans.pop()
			root.left = ans.pop()
			ans.append(root)
		else:
			ans.append(et(i + ' '))
	return ans[0]


def constructTree(postfix):
	stack = []
	root = None
	for ch in postfix:
		if not isOperator(ch):
			stack.append(et(ch + ' '))
		else:
			root = et(ch + ' ')
			(root.right, root.left) = (stack.pop(), stack.pop())
			stack.append(root)
	return stack.pop()


def constructTree(postfix):
	stack = []
	root = None
	for ch in postfix:
		if not isOperator(ch):
			stack.append(et(ch + ' '))
		else:
			(a, b) = (stack.pop(), stack.pop())
			root = et(ch + ' ')
			root.left = b
			root.right = a
			stack.append(root)
	result = stack.pop()
	return result

def is_operand(ch):
	return True if ch.isalnum() and ch not in ['+', '-', '*', '/', '^'] else False


def constructTree(postfix):
	st = []
	for i in postfix:
		if i.isalpha():
			nt = et(i + ' ')
			st.append(nt)
		else:
			a = st.pop()
			b = st.pop()
			nt = et(i + ' ')
			nt.left = b
			nt.right = a
			st.append(nt)
	return st[-1]


def constructTree(postfix):
	if postfix == '':
		return None

	def postFixToET(postfix, ptr):
		elem = postfix[ptr[0]]
		node = et(elem + ' ')
		ptr[0] -= 1
		if isOperator(elem):
			node.right = postFixToET(postfix, ptr)
			node.left = postFixToET(postfix, ptr)
		return node
	postfix = list(postfix)
	return postFixToET(postfix, [len(postfix) - 1])


def constructTree(postfix):
	n = len(postfix)
	index = n - 1

	def util():
		nonlocal index
		data = postfix[index]
		index -= 1
		if isOperator(data):
			root = et(' ' + data + ' ')
			root.right = util()
			root.left = util()
		else:
			root = et(data)
		return root
	return util()


def constructTree(postfix):
	if len(postfix) == 0:
		return None
	stack = []
	for char in postfix:
		if not isOperator(char):
			stack.append(et(char))
		else:
			(two, one) = (stack.pop(), stack.pop())
			node = et(' ' + char + ' ')
			(node.left, node.right) = (one, two)
			stack.append(node)
	return stack[-1]


def constructTree(postfix):
	chars = list(postfix)
	for i in chars:
		if i.isalpha():
			print(i, end=' ')
			last = chars.pop()
			if not last.isalpha():
				print(last, end=' ')


def constructTree(postfix):
	chars = []
	sym = []
	for i in postfix:
		if i.isalpha():
			chars.append(i)
		else:
			sym.append(i)
	for j in chars:
		if sym:
			print(j + ' ' + sym.pop(), end=' ')
		else:
			print(j, end='')


def constructTree(postfix):
	stack = []
	for c in postfix:
		node = et(c + ' ')
		if not isOperator(c):
			stack.append(node)
		elif isOperator(c):
			right = stack.pop()
			left = stack.pop()
			node.left = left
			node.right = right
			stack.append(node)
	return node