Given a full binary expression tree consisting of basic binary operators (+, -,*, /) and some integers, Your task is to evaluate the expression tree.
Example 1:
Input: 
              +
           /     \
          *       -
        /  \    /   \
       5    4  100  20 
Output: 100
Explanation:
((5 * 4) + (100 - 20)) = 100
Example 2:
Input:
            -
          /   \
         4     7
Output: -3
Explanation:
4 - 7 = -3
Your Task:  
You dont need to read input or print anything. Complete the function evalTree() which takes root node as input parameter and returns an integer denoting the result obtained by simplifying the expression tree.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(height of tree)
Constraints:
1 ≤ N ≤ 500

Difficulty: EASY
Tags: Tree algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(height of tree)

Starter code:
# Your task is to complete this function



class Solution:

    # function should return an integer denoting the required answer

    def evalTree(self, root):

        # Code here



Solutions:
class Solution:

	def evalTree(self, root):
		if root.left is None and root.right is None:
			return int(root.data)
		if root.data == '+':
			return self.evalTree(root.left) + self.evalTree(root.right)
		if root.data == '-':
			return self.evalTree(root.left) - self.evalTree(root.right)
		if root.data == '*':
			return self.evalTree(root.left) * self.evalTree(root.right)
		if root.data == '/':
			return int(self.evalTree(root.left) / self.evalTree(root.right))


class Solution:

	def evalTree(self, root):

		def answer(root):
			if root.data != '+' and root.data != '-' and (root.data != '*') and (root.data != '/'):
				return int(root.data)
			else:
				ls = answer(root.left)
				rs = answer(root.right)
				if root.data == '+':
					return ls + rs
				elif root.data == '*':
					return ls * rs
				elif root.data == '-':
					return ls - rs
				elif root.data == '/':
					if ls // rs < 0 and ls / rs != ls // rs:
						return ls // rs + 1
					return ls // rs
		return answer(root)


class Solution:

	def evalTree(self, root):
		if root is None:
			return -1
		if root.left is None and root.right is None:
			return int(root.data)
		leftsum = self.evalTree(root.left)
		rightsum = self.evalTree(root.right)
		if root.data == '+':
			return leftsum + rightsum
		elif root.data == '-':
			return leftsum - rightsum
		elif root.data == '*':
			return leftsum * rightsum
		else:
			return int(leftsum / rightsum)


class Solution:

	def evalTree(self, root):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return int(root.data)
		l = self.evalTree(root.left)
		r = self.evalTree(root.right)
		if root.data == '+':
			return l + r
		elif root.data == '-':
			return l - r
		elif root.data == '*':
			return l * r
		else:
			return int(l / r)


class Solution:

	def evalTree(self, root):
		if root.left == root.right == None:
			return str(root.data)
		return int(eval(str(self.evalTree(root.left)) + str(root.data) + str(str(self.evalTree(root.right)))))


class Solution:

	def evalTree(self, root):
		if root.data != '*' and root.data != '/' and (root.data != '+') and (root.data != '-'):
			return int(root.data)
		leftval = self.evalTree(root.left)
		rightval = self.evalTree(root.right)
		exp = root.data
		if exp == '+':
			return leftval + rightval
		if exp == '-':
			return leftval - rightval
		if exp == '*':
			return leftval * rightval
		if exp == '/':
			return int(leftval / rightval)
		return 0


class Solution:

	def evalTree(self, root):
		res = []

		def postorder(root):
			if root:
				postorder(root.left)
				postorder(root.right)
				res.append(root.data)
		postorder(root)
		stack = []
		lis = ['+', '*', '/', '-']
		for i in res:
			if i not in lis:
				stack.append(i)
			elif i == '+':
				op1 = stack.pop()
				op2 = stack.pop()
				op3 = int(op2) + int(op1)
				stack.append(op3)
			elif i == '-':
				op1 = stack.pop()
				op2 = stack.pop()
				op3 = int(op2) - int(op1)
				stack.append(op3)
			elif i == '*':
				op1 = stack.pop()
				op2 = stack.pop()
				op3 = int(op2) * int(op1)
				stack.append(op3)
			elif i == '/':
				op1 = stack.pop()
				op2 = stack.pop()
				op3 = int(op2) / int(op1)
				stack.append(op3)
		return int(stack[0])


class Solution:

	def evalTree(self, node):
		if node.right is None and node.left is None:
			return node.data
		if node.data == '+':
			return int(self.evalTree(node.left)) + int(self.evalTree(node.right))
		elif node.data == '-':
			return int(self.evalTree(node.left)) - int(self.evalTree(node.right))
		elif node.data == '*':
			return int(self.evalTree(node.left)) * int(self.evalTree(node.right))
		elif node.data == '/':
			return int(int(self.evalTree(node.left)) / int(self.evalTree(node.right)))


class Solution:

	def evalTree(self, root):
		return self.ans(root)

	def ans(self, root):
		if not root:
			return
		if not root.right and (not root.left):
			return root.data
		return int(eval(str(self.ans(root.left)) + root.data + str(self.ans(root.right))))


class Solution:

	def evalTree(self, root):
		if not root.left and (not root.right):
			return int(root.data)
		el = root.data
		if el == '-':
			return int(self.evalTree(root.left) - self.evalTree(root.right))
		if el == '*':
			return int(self.evalTree(root.left) * self.evalTree(root.right))
		if el == '/':
			return int(self.evalTree(root.left) / self.evalTree(root.right))
		if el == '+':
			return int(self.evalTree(root.left) + self.evalTree(root.right))


class Solution:

	def evalTree(self, root):
		if not root:
			return
		if root.data.isdigit():
			return root.data
		left = str(self.evalTree(root.left))
		right = str(self.evalTree(root.right))
		return int(eval(left + root.data + right))


class Solution:

	def evalTree(self, root):

		def sol(root):
			if root == None:
				return 1
			else:
				left = sol(root.left)
				right = sol(root.right)
				if root.data == '+':
					return int(left) + int(right)
				elif root.data == '-':
					return int(left) - int(right)
				elif root.data == '*':
					return int(left) * int(right)
				elif root.data == '/':
					return int(int(left) / int(right))
				return root.data
		k = sol(root)
		return k


class Solution:

	def evalTrees(self, root):
		if not root:
			return 0
		if not root.left and (not root.right):
			return int(root.data)
		a = self.evalTrees(root.left)
		b = self.evalTrees(root.right)
		if root.data == '+':
			return a + b
		elif root.data == '-':
			return a - b
		elif root.data == '*':
			return a * b
		elif root.data == '/':
			return int(a / b)

	def evalTree(self, root):
		return self.evalTrees(root)


class Solution:

	def evalTree(self, root):
		if root == None:
			return 0
		if root.data == '+':
			return self.evalTree(root.left) + self.evalTree(root.right)
		elif root.data == '-':
			return self.evalTree(root.left) - self.evalTree(root.right)
		elif root.data == '*':
			return self.evalTree(root.left) * self.evalTree(root.right)
		elif root.data == '/':
			return int(self.evalTree(root.left) / self.evalTree(root.right))
		else:
			return int(root.data)


class Solution:

	def evalTree(self, root):
		return self.x(root)

	def x(self, root):
		if root is None:
			return
		left = self.x(root.left)
		right = self.x(root.right)
		if root.data == '*':
			return left * right
		elif root.data == '-':
			return left - right
		elif root.data == '+':
			return left + right
		elif root.data == '/':
			return int(left / right)
		return int(root.data)


class Solution:

	def evalTree(self, root):

		def traversal(root):
			if root == None:
				return None
			if root.left:
				traversal(root.left)
			if root.right:
				traversal(root.right)
			if root.data == '+':
				root.data = int(root.left.data) + int(root.right.data)
			elif root.data == '-':
				root.data = int(root.left.data) - int(root.right.data)
			elif root.data == '*':
				root.data = int(root.left.data) * int(root.right.data)
			elif root.data == '/':
				root.data = int(root.left.data) / int(root.right.data)
		traversal(root)
		return int(root.data)


class Solution:

	def evalTree(self, root):
		if not root.left and (not root.right):
			return int(root.data)
		l = self.evalTree(root.left)
		r = self.evalTree(root.right)
		if root.data == '+':
			return l + r
		if root.data == '-':
			return l - r
		if root.data == '*':
			return l * r
		if root.data == '/':
			return int(l / r)


class Solution:

	def evalTree(self, root):
		if root == None:
			return 0
		elif not root.left and (not root.right):
			return int(root.data)
		elif root.data == '+':
			return int(self.evalTree(root.left)) + int(self.evalTree(root.right))
		elif root.data == '-':
			return int(self.evalTree(root.left)) - int(self.evalTree(root.right))
		elif root.data == '*':
			return int(self.evalTree(root.left)) * int(self.evalTree(root.right))
		elif root.data == '/':
			return int(int(self.evalTree(root.left)) / int(self.evalTree(root.right)))
		else:
			return -1


class Solution:

	def evalTree(self, root):

		def Eval(Node):
			if Node.left == None and Node.right == None:
				return int(Node.data)
			ExpL = Eval(Node.left)
			ExpR = Eval(Node.right)
			if Node.data == '/':
				return int(ExpL / ExpR)
			elif Node.data == '*':
				return ExpL * ExpR
			elif Node.data == '+':
				return ExpL + ExpR
			elif Node.data == '-':
				return ExpL - ExpR
			else:
				return Node.data
		return int(Eval(root))


class Solution:

	def evalTree(self, root):
		if not root:
			return 0
		if self.isLeaf(root):
			return int(root.data)
		l = self.evalTree(root.left)
		r = self.evalTree(root.right)
		if self.isExpression(root.data):
			root.data = self.calculate(root.data, l, r)
		return int(root.data)

	def isExpression(self, data):
		return data == '+' or data == '-' or data == '*' or (data == '/')

	def calculate(self, data, l, r):
		if data == '+':
			return l + r
		elif data == '-':
			return l - r
		elif data == '*':
			return l * r
		elif data == '/':
			return l / r

	def isLeaf(self, root):
		return not root.left and (not root.right)


class Solution:

	def evalTree(self, root):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return int(root.data)
		left_sum = self.evalTree(root.left)
		right_sum = self.evalTree(root.right)
		if root.data == '+':
			return left_sum + right_sum
		elif root.data == '-':
			return left_sum - right_sum
		elif root.data == '*':
			return left_sum * right_sum
		else:
			return int(left_sum / right_sum)


class Solution:

	def evalTree(self, root):

		def helper(root):
			if root.data.isdigit():
				return int(root.data)
			left = helper(root.left)
			right = helper(root.right)
			op = root.data
			if op == '+':
				return left + right
			elif op == '-':
				return left - right
			elif op == '*':
				return left * right
			elif op == '/':
				if right != 0:
					return int(left / right)
				else:
					return -1
		return helper(root)


class Solution:

	def evalTree(self, root):
		if not root:
			return 0
		if not root.left and (not root.right):
			return int(root.data)
		lst = self.evalTree(root.left)
		rst = self.evalTree(root.right)
		if root.data == '+':
			return lst + rst
		elif root.data == '-':
			return lst - rst
		elif root.data == '*':
			return lst * rst
		elif root.data == '/':
			return int(lst / rst)


class Solution:

	def evalTree(self, root):
		if not root:
			return 0
		if not root.left and (not root.right):
			return int(root.data)
		l = self.evalTree(root.left)
		r = self.evalTree(root.right)
		return int(eval(str(l) + root.data + str(r)))


class Solution:

	def evalTree(self, root):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return int(root.data)
		lv = self.evalTree(root.left)
		rv = self.evalTree(root.right)
		if root.data == '*':
			return lv * rv
		elif root.data == '+':
			return lv + rv
		elif root.data == '-':
			return lv - rv
		else:
			return int(lv / rv)


class Solution:

	def evalTree(self, root):
		if not root:
			return 0
		if root.data not in ['+', '-', '*', '/']:
			return int(root.data)
		if root.data == '+':
			return self.evalTree(root.left) + self.evalTree(root.right)
		if root.data == '-':
			return self.evalTree(root.left) - self.evalTree(root.right)
		if root.data == '*':
			return self.evalTree(root.left) * self.evalTree(root.right)
		if root.data == '/':
			return int(self.evalTree(root.left) / self.evalTree(root.right))


class Solution:

	def solve(self, n):
		if n.left is None and n.right is None:
			return int(n.data)
		if n is None:
			return 0
		sign = n.data
		left = self.solve(n.left)
		right = self.solve(n.right)
		if sign == '+':
			return left + right
		if sign == '-':
			return left - right
		if sign == '*':
			return left * right
		if sign == '/':
			return int(left / right)

	def evalTree(self, root):
		return self.solve(root)


class Solution:

	def isLeaf(self, root):
		if not root.left and (not root.right):
			return True
		return False

	def eval(self, sign, x, y):
		try:
			x = int(x)
			y = int(y)
		except:
			return 24

	def evalTree(self, root):
		if not root:
			return 0
		if not root.left and (not root.right):
			return int(root.data)
		x = self.evalTree(root.left)
		y = self.evalTree(root.right)
		sign = root.data
		if sign == '*':
			return x * y
		elif sign == '+':
			return x + y
		elif sign == '-':
			return x - y
		else:
			return int(x / y)


class Solution:

	def evalTree(self, root):

		def evaluate(node):
			if node.right == None and node.left == None:
				return int(node.data)
			left = evaluate(node.left)
			right = evaluate(node.right)
			if node.data == '*':
				return left * right
			elif node.data == '+':
				return left + right
			elif node.data == '-':
				return left - right
			else:
				return int(left / right)
		return evaluate(root)


class Solution:

	def evalTree(self, root):

		def helper(x):
			if not x:
				return 0
			if x.left == None and x.right == None:
				return x.data
			l = helper(x.left)
			r = helper(x.right)
			if x.data == '+':
				return int(l) + int(r)
			if x.data == '-':
				return int(l) - int(r)
			if x.data == '*':
				return int(l) * int(r)
			if x.data == '/':
				return int(int(l) / int(r))
		a = helper(root)
		return a


class Solution:

	def evalTree(self, root):
		if not root:
			return 0
		if root.data not in ['+', '-', '*', '/']:
			return int(root.data)
		l = self.evalTree(root.left)
		r = self.evalTree(root.right)
		if root.data == '+':
			return l + r
		elif root.data == '-':
			return l - r
		elif root.data == '*':
			return l * r
		else:
			return int(l / r)


class Solution:

	def evalTree(self, root):
		if not root:
			return 0
		if root.left == None and root.right == None:
			return int(root.data)
		if type(root.data) is int:
			return int(root.data)
		if root.data == '+':
			return self.evalTree(root.left) + self.evalTree(root.right)
		if root.data == '-':
			return self.evalTree(root.left) - self.evalTree(root.right)
		if root.data == '*':
			return self.evalTree(root.left) * self.evalTree(root.right)
		if root.data == '/':
			return int(self.evalTree(root.left) / self.evalTree(root.right))


class Solution:
	OPS = ['+', '-', '*', '/']

	def get_val(self, a, b, op):
		if op == '+':
			return a + b
		elif op == '-':
			return a - b
		elif op == '*':
			return a * b
		elif op == '/':
			return a / b

	def eval(self, root):
		if root.data not in self.OPS:
			return root.data
		lst_val = self.eval(root.left)
		rst_val = self.eval(root.right)
		return self.get_val(int(lst_val), int(rst_val), root.data)

	def evalTree(self, root):
		exp_val = self.eval(root)
		return int(exp_val)


class Solution:

	def evalTree(self, root):

		def rec(root):
			if not root.left and (not root.right):
				return root.data
			return self.evaluate(rec(root.left), rec(root.right), root.data)
		res = rec(root)
		return int(res)

	def evaluate(self, op1, op2, op):
		(op1, op2) = (int(op1), int(op2))
		if op == '+':
			return op1 + op2
		if op == '-':
			return op1 - op2
		if op == '*':
			return op1 * op2
		if op == '/':
			return op1 / op2


class Solution:

	def evalTree(self, root):
		if not root:
			return 0
		if root.left is None and root.right is None:
			return int(root.data)
		leftSum = self.evalTree(root.left)
		rightSum = self.evalTree(root.right)
		if root.data == '+':
			return leftSum + rightSum
		elif root.data == '-':
			return leftSum - rightSum
		elif root.data == '*':
			return leftSum * rightSum
		return int(leftSum / rightSum)


class Solution:

	def evalTree(self, root):
		if root == None:
			return 0
		if root.left is None and root.right is None:
			return int(root.data)
		lt = self.evalTree(root.left)
		rt = self.evalTree(root.right)
		if root.data == '+':
			return lt + rt
		if root.data == '-':
			return lt - rt
		if root.data == '*':
			return lt * rt
		if root.data == '/':
			return int(lt / rt)


class Solution:

	def evalTree(self, root):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return int(root.data)
		lans = self.evalTree(root.left)
		rans = self.evalTree(root.right)
		if root.data == '+':
			return lans + rans
		elif root.data == '-':
			return lans - rans
		elif root.data == '*':
			return lans * rans
		return int(lans / rans)


class Solution:

	def evalTree(self, root):
		if root.data.isnumeric():
			return int(root.data)
		leftResult = self.evalTree(root.left)
		rightResult = self.evalTree(root.right)
		if root.data == '+':
			return int(leftResult + rightResult)
		if root.data == '-':
			return int(leftResult - rightResult)
		if root.data == '*':
			return int(leftResult * rightResult)
		if root.data == '/':
			return int(leftResult / rightResult)


class Solution:

	def evalTree(self, root):

		def traversal(root):
			if root == None:
				return 0
			if root.left == None and root.right == None:
				return int(root.data)
			L = traversal(root.left)
			R = traversal(root.right)
			if root.data == '*':
				return L * R
			elif root.data == '/':
				return int(L / R)
			elif root.data == '+':
				return L + R
			elif root.data == '-':
				return L - R
		return traversal(root)


import math

class Solution:

	def evalTree(self, root):

		def f(root):
			if root == None:
				return 0
			if root.left == None and root.right == None:
				return int(root.data)
			x = f(root.left)
			y = f(root.right)
			if root.data == '*':
				return x * y
			elif root.data == '-':
				return x - y
			elif root.data == '+':
				return x + y
			elif root.data == '/':
				return int(x / y)
		return f(root)


import math

class Solution:

	def evalTree(self, root):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return int(root.data)
		leftsum = self.evalTree(root.left)
		rightsum = self.evalTree(root.right)
		if root.data == '+':
			return leftsum + rightsum
		elif root.data == '-':
			return leftsum - rightsum
		elif root.data == '*':
			return leftsum * rightsum
		return int(leftsum / rightsum)


class Solution:

	def evalTree(self, root):

		def helper(root):
			if root.left == None and root.right == None:
				return root.data
			lh = helper(root.left)
			rh = helper(root.right)
			if root.data == '+':
				return int(lh) + int(rh)
			if root.data == '-':
				return int(lh) - int(rh)
			if root.data == '*':
				return int(lh) * int(rh)
			if root.data == '/':
				return int(lh) / int(rh)
		return int(helper(root))


class Solution:

	def evalTree(self, root):
		if not root:
			return 0
		if not root.left and (not root.right):
			return int(root.data)
		ls = self.evalTree(root.left)
		rs = self.evalTree(root.right)
		if root.data == '+':
			return ls + rs
		elif root.data == '-':
			return ls - rs
		elif root.data == '*':
			return ls * rs
		return int(ls / rs)


class Solution:

	def evalTree(self, root):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return int(root.data)
		operand1 = self.evalTree(root.left)
		operand2 = self.evalTree(root.right)
		if root.data == '+':
			return operand1 + operand2
		elif root.data == '-':
			return operand1 - operand2
		elif root.data == '*':
			return operand1 * operand2
		else:
			return int(operand1 / operand2)


class Solution:

	def get_string(self, root):
		if root is None:
			return root
		self.get_string(root.left)
		self.get_string(root.right)
		exp = ['+', '-', '*', '/']
		if root.data in exp and root.left.data not in exp:
			root.data = int(self.do_the_math(root.data, int(root.left.data), int(root.right.data)))

	def do_the_math(self, a, b, c):
		if a == '+':
			return b + c
		if a == '-':
			return b - c
		if a == '*':
			return b * c
		if a == '/':
			return b / c

	def evalTree(self, root):
		self.get_string(root)
		return root.data


class Solution:

	def evalTree(self, root):
		temp = ['+', '-', '*', '/']
		result = self.evalTreeUtil(root)
		if str(result)[0] in temp:
			a = str(result)[0]
			b = ''
			for i in range(1, len(str(result))):
				if str(result)[i] == '.':
					break
				b += str(result)[i]
			return a + b
		else:
			return int(result)

	def evalTreeUtil(self, root):
		if str(root.data).isdigit() or str(root.data).isdigit():
			if str(root.data).isdigit():
				return root.data
			else:
				return root.data
		left = self.evalTreeUtil(root.left)
		right = self.evalTreeUtil(root.right)
		return int(eval(str(left) + str(root.data) + str(right)))


class Solution:

	def evalTree(self, root):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return int(root.data)
		leftsum = self.evalTree(root.left)
		rightsum = self.evalTree(root.right)
		if root.data == '+':
			return leftsum + rightsum
		elif root.data == '-':
			return leftsum - rightsum
		elif root.data == '*':
			return leftsum * rightsum
		return int(leftsum / rightsum)

class node:

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

def isExp(s):
	if s == '+' or s == '-' or s == '*' or (s == '/'):
		return True
	return False
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = input().strip().split()
		q = []
		p = 0
		root = node(arr[p])
		q.append(root)
		p = 1
		while q != []:
			f = q.pop(0)
			if isExp(f.data):
				l = node(arr[p])
				p += 1
				r = node(arr[p])
				p += 1
				f.left = l
				f.right = r
				q.append(l)
				q.append(r)
		print(Solution().evalTree(root))