Given a binary tree and a number K, the task is to find sum of tree nodes at level K. The Binary Tree is given in string form S: (node-value(left-subtree)(right-subtree)).
 
Example 1:
Input:
K = 2
S = "(0(5(6()())(4()(9()())))(7(1()())(3()())))"
Output:
14
Explanation:
The Tree from the above String will be formed as:
                             0
                           /   \
                          5      7
                        /  \    /  \
                       6    4  1    3
                             \
                              9  
Sum of nodes at the 2nd level is 6+4+1+3 = 14.
Example 1:
Input:
K = 1
S = "(4(8()9())"
Output:
17
Explanation:
The Tree from the above String will be formed as:
                             4
                           /   \
                          8     9
Sum of nodes at the 1st level is 8+9 = 17.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function kLevelSum() which takes an Integer K and a String S as input and returns the sum of all the node values at Kth level of the tree.
 
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
 
Constraints:
5 <= |S| <= 10^{5}
0 <= K <= 15

Difficulty: EASY
Tags: Tree algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def kLevelSum(self, K, S):

        # code here 

Solutions:
class Solution:

	def kLevelSum(self, K, S):
		h = -1
		res = 0
		i = 0
		while i < len(S):
			if S[i] == '(':
				h += 1
				i += 1
			elif S[i] == ')':
				h -= 1
				i += 1
			elif h == K:
				tmp = ''
				while S[i] in '0123456789':
					tmp += S[i]
					i += 1
				if tmp:
					res = res + int(tmp)
				else:
					res += int(i)
					i += 1
			else:
				i += 1
		return res


class Solution:

	def kLevelSum(self, K, S):
		st = []
		ans = 0
		l = ''
		for i in range(len(S)):
			if st:
				if st[-1] == '(' and S[i] == ')':
					st.pop()
				if S[i] == '(':
					st.append(S[i])
				if len(st) == K + 1:
					if S[i].isdigit():
						l += S[i]
					else:
						if l != '':
							ans += int(l)
						l = ''
			elif S[i] == '(':
				st.append(S[i])
		return ans


class Solution:

	def kLevelSum(self, K, S):
		o = 0
		s = 0
		i = 0
		while i < len(S):
			if S[i] == '(':
				o += 1
			elif S[i] == ')':
				o -= 1
			elif o == K + 1:
				n = 0
				while S[i] != '(' and S[i] != ')':
					n = n * 10 + int(S[i])
					i = i + 1
				i -= 1
				s = s + n
			i += 1
		return s


class Solution:

	def kLevelSum(self, K, S):
		d = {}
		l = []
		l1 = []
		visited = []
		for i in range(len(S)):
			if i not in visited:
				if S[i] == '(':
					l.append(S[i])
				elif S[i] == ')':
					l.pop()
				else:
					a = l.count('(')
					s = ''
					while S[i] not in ['(', ')']:
						s += S[i]
						visited.append(i)
						i += 1
						if i < len(S):
							pass
						else:
							break
					if a not in d:
						d[a] = [int(s)]
					else:
						d[a].append(int(s))
		return sum(d[K + 1])


class Solution:

	def kLevelSum(self, K, S):
		(i, n) = (0, len(S))
		ans = 0
		level = -1
		while i < n:
			if S[i] == '(':
				level += 1
			elif S[i] == ')':
				level -= 1
			elif level == K:
				temp = int(S[i])
				while i + 1 < n and S[i + 1] != '(':
					i += 1
					temp = 10 * temp + int(S[i])
				ans += temp
			i += 1
		return ans


class Solution:

	def kLevelSum(self, K, S):
		level = -1
		sumOfKLevel = 0
		ind = 0
		while ind < len(S):
			if S[ind] == '(':
				level += 1
			if level == K and S[ind].isdigit():
				num = []
				while S[ind].isdigit():
					num.append(S[ind])
					ind += 1
				sumOfKLevel += int(''.join(num))
				ind -= 1
			if S[ind] == ')':
				level -= 1
			ind += 1
		return sumOfKLevel


class Solution:

	def kLevelSum(self, K, S):
		count = 0
		summa = 0
		num = ''
		for item in S:
			count += item is '('
			count -= item is ')'
			if count == K + 1 and item.isdigit():
				num += item
			elif num:
				summa += int(num)
				num = ''
		return summa


class Solution:

	def kLevelSum(self, K, S):
		if K == 0:
			return S[1]
		level = 0
		sum = 0
		i = 2
		while i < len(S):
			if S[i] == '(':
				level += 1
			if S[i] == ')':
				level -= 1
			if level == K and (S[i] != '(' and S[i] != ')'):
				h = S[i]
				while S[i + 1] != '(' and S[i + 1] != ')':
					h += S[i + 1]
					i += 1
				sum = sum + int(h)
			i += 1
		return sum


class Solution:

	def kLevelSum(self, K, S):
		i = 0
		level = -1
		summ = 0
		while i < len(S):
			if S[i] == '(':
				level += 1
				i += 1
			elif S[i] == ')':
				level -= 1
				i += 1
			elif level == K:
				s = ''
				while i < len(S) and S[i] != ')' and (S[i] != '('):
					s += S[i]
					i += 1
				summ += int(s)
			else:
				i += 1
		return summ


class Solution:

	def kLevelSum(self, K, S):
		c = 0
		ans = 0
		i = 0
		while i < len(S):
			if S[i] == '(':
				c += 1
				i += 1
			elif S[i] == ')':
				c -= 1
				i += 1
			else:
				num = 0
				x = i
				d = 10
				while S[x] != '(' and S[x] != ')':
					num = num * d + int(S[x])
					x += 1
				i = x
				if c == K + 1:
					ans += num
		return ans


class Solution:

	def kLevelSum(self, K, S):
		stack = []
		(add, b) = (0, 0)
		while b < len(S):
			if len(stack) == K + 1 and S[b].isnumeric():
				i = b
				tmp = ''
				while S[i].isnumeric():
					tmp += S[i]
					i += 1
				add += int(tmp)
				b = i
			if S[b].isnumeric() == False:
				if S[b] == ')':
					stack.pop()
				else:
					stack.append(S[b])
			b += 1
		return add


class Solution:

	def kLevelSum(self, K, S):
		count = -1
		sumk = 0
		i = 0
		while i < len(S):
			if count == K and S[i] != ')' and (S[i] != '('):
				h = ''
				while S[i] != '(' and S[i] != ')':
					h += S[i]
					i += 1
				sumk += int(h)
			if S[i] == '(':
				count += 1
				i += 1
			elif S[i] == ')':
				count -= 1
				i += 1
			else:
				i += 1
		return sumk


class Solution:

	def kLevelSum(self, K, S):
		(add, index) = (0, 0)
		stack = []
		while index < len(S):
			if len(stack) == K + 1 and S[index].isnumeric():
				integer_index = index
				temp_number = ''
				while S[integer_index].isnumeric():
					temp_number += S[integer_index]
					integer_index += 1
				add += int(temp_number)
				index = integer_index
			if not S[index].isnumeric():
				if S[index] == '(':
					stack.append(S[index])
				if S[index] == ')':
					stack.pop()
			index += 1
		return add


class Solution:

	def kLevelSum(self, K, S):
		layer = 0
		ans = 0
		val = 0
		K += 1
		for i in S:
			if i == '(':
				if layer == K:
					ans += val
				layer += 1
				val = 0
			elif i == ')':
				layer -= 1
			else:
				val = int(i) + val * 10
		return ans


class Solution:

	def kLevelSum(self, k, s):
		(level, ans, i) = (0, 0, 0)
		while i < len(s):
			if s[i] == '(':
				level += 1
				i += 1
			elif s[i] == ')':
				level -= 1
				i += 1
			elif level == k + 1:
				last = i
				while i < len(s):
					if s[i] == '(':
						level += 1
						break
					if s[i] == ')':
						level -= 1
						break
					i += 1
				ans += int(s[last:i])
				i += 1
			else:
				i += 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		K = int(input())
		S = input()
		ob = Solution()
		print(ob.kLevelSum(K, S))


from collections import defaultdict

class Solution:

	def kLevelSum(self, K, S):
		l = 0
		level = defaultdict(list)
		i = 0
		while i < len(S):
			if S[i] == '(':
				l += 1
				i += 1
			elif S[i] == ')':
				l -= 1
				i += 1
			else:
				s = ''
				while S[i] != '(' and S[i] != ')':
					s += S[i]
					i += 1
				level[l].append(int(s))
		return sum(level[K + 1])


class Solution:

	def kLevelSum(self, K, S):
		lsum = 0
		level = -1
		nodes = []
		i = 0
		while i < len(S):
			digit = ''
			if S[i] == '(':
				level += 1
			if S[i] == ')':
				level -= 1
			while level == K and S[i] not in ['(', ')']:
				digit += S[i]
				i = i + 1
				if S[i] == '(':
					i -= 1
					break
			if digit:
				nodes.append(int(digit))
			i += 1
		return sum(nodes)


class Solution:

	def kLevelSum(self, K, S):
		level = -1
		s = 0
		num = '0'
		for i in range(len(S)):
			if S[i] == '(':
				s += int(num)
				num = '0'
				level += 1
			elif S[i] == ')':
				s += int(num)
				num = '0'
				level -= 1
			elif level == K:
				num += S[i]
		return s


class Solution:

	def kLevelSum(self, K, S):
		n = 0
		l = []
		l1 = []
		l[:0] = S
		jk = []
		kll = []
		for i in l:
			if i == '(' or i == ')':
				if len(kll) != 0:
					hj = ''.join(kll)
					jk.append(int(hj))
					kll = []
				l1.append(i)
			kl = len(l1)
			if kl - 1 == K:
				if i.isnumeric():
					kll.append(i)
			if i == ')' and l1[kl - 2] == '(':
				l1.pop(kl - 1)
				l1.pop(kl - 2)
		return sum(jk)


class Solution:

	def kLevelSum(self, K, S):
		count = -1
		ans = 0
		i = 0
		while i < len(S):
			if S[i] == '(':
				count += 1
			elif S[i] == ')':
				count -= 1
			if count == K and S[i] != '(' and (S[i] != ')'):
				sum = int(S[i])
				i += 1
				if i >= len(S):
					return ans
				while S[i] >= '0' and S[i] <= '9':
					if i >= len(S):
						return ans
					sum *= 10
					sum += int(S[i])
					i += 1
				ans += sum
				if S[i] == '(':
					count += 1
				if S[i] == ')':
					count -= 1
			i += 1
		return ans


class Solution:

	def kLevelSum(self, K, S):
		c = -1
		(ans, i, su) = (0, 0, 0)
		while i < len(S):
			if S[i] == '(':
				c += 1
			elif S[i] == ')':
				c -= 1
			if c == K and S[i] != '(' and (S[i] != ')'):
				su = int(S[i])
				i += 1
				if i >= len(S):
					return ans
				while S[i] >= '0' and S[i] <= '9':
					su = su * 10 + int(S[i])
					i += 1
				ans += su
				if S[i] == '(':
					c += 1
				elif S[i] == ')':
					c -= 1
			i += 1
		return ans


class Solution:

	def kLevelSum(self, K, S):
		lvl = -1
		Sum = 0
		N = len(S)
		i = 0
		while i < N:
			if S[i] == '(':
				lvl += 1
			elif S[i] == ')':
				lvl -= 1
			elif S[i].isdigit():
				if lvl == K:
					num = 0
					while i < N:
						if S[i] == '(' or S[i] == ')':
							i -= 1
							break
						num = num * 10 + int(S[i])
						i += 1
					Sum += num
			i += 1
		return Sum


class Solution:

	def kLevelSum(self, K, S):
		lvl = -1
		res = 0
		temp = ''
		for i in S:
			if i == '(':
				lvl += 1
				if temp:
					res += int(temp)
					temp = ''
			elif i == ')':
				lvl -= 1
				if temp:
					res += int(temp)
					temp = ''
			elif lvl == K:
				temp += i
		return res