# Sum of nodes at k-th level in a tree represented as string

Given an integer ‘K’ and a binary tree in string format. Every node of a tree has value in range from 0 to 9. We need to find sum of elements at K-th level from root. The root is at level 0.
Tree is given in the form: (node value(left subtree)(right subtree))

Examples:

```Input : tree = "(0(5(6()())(4()(9()())))(7(1()())(3()())))"
k = 2
Output : 14
Its tree representation is shown below

Elements at level k = 2 are 6, 4, 1, 3
sum of the digits of these elements = 6+4+1+3 = 14

Input : tree = "(8(3(2()())(6(5()())()))(5(10()())(7(13()())())))"
k = 3
Output : 9
Elements at level k = 3 are 5, 1 and 3
sum of digits of these elements = 5+1+3 = 9
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

```1. Input 'tree' in string format and level k
2. Initialize level = -1 and sum = 0
3. for each character 'ch' in 'tree'
3.1  if ch == '(' then
--> level++
3.2  else if ch == ')' then
--> level--
3.3  else
if level == k then
sum = sum + (ch-'0')
4. Print sum
```

## C++

 `// C++ implementation to find sum of ` `// digits of elements at k-th level ` `#include ` `using` `namespace` `std; ` ` `  `// Function to find sum of digits ` `// of elements at k-th level ` `int` `sumAtKthLevel(string tree, ``int` `k) ` `{ ` `    ``int` `level = -1; ` `    ``int` `sum = 0;  ``// Initialize result ` `    ``int` `n = tree.length(); ` ` `  `    ``for` `(``int` `i=0; i

## Java

 `// Java implementation to find sum of  ` `// digits of elements at k-th level  ` `class` `GfG {  ` ` `  `// Function to find sum of digits  ` `// of elements at k-th level  ` `static` `int` `sumAtKthLevel(String tree, ``int` `k)  ` `{  ` `    ``int` `level = -``1``;  ` `    ``int` `sum = ``0``; ``// Initialize result  ` `    ``int` `n = tree.length();  ` ` `  `    ``for` `(``int` `i=``0``; i

## Python3

 `# Python3 implementation to find sum of  ` `# digits of elements at k-th level  ` ` `  `# Function to find sum of digits  ` `# of elements at k-th level  ` `def` `sumAtKthLevel(tree, k) : ` ` `  `    ``level ``=` `-``1` `    ``sum` `=` `0` `# Initialize result  ` `    ``n ``=` `len``(tree)  ` ` `  `    ``for` `i ``in` `range``(n): ` `         `  `        ``# increasing level number  ` `        ``if` `(tree[i] ``=``=` `'('``) : ` `            ``level ``+``=` `1` ` `  `        ``# decreasing level number  ` `        ``elif` `(tree[i] ``=``=` `')'``):  ` `            ``level ``-``=` `1` ` `  `        ``else``: ` `         `  `            ``# check if current level is  ` `            ``# the desired level or not  ` `            ``if` `(level ``=``=` `k) : ` `                ``sum` `+``=` `(``ord``(tree[i]) ``-` `ord``(``'0'``))  ` `         `  `    ``# required sum  ` `    ``return` `sum` ` `  `# Driver Code  ` `if` `__name__ ``=``=` `'__main__'``: ` `    ``tree ``=` `"(0(5(6()())(4()(9()())))(7(1()())(3()())))"` `    ``k ``=` `2` `    ``print``(sumAtKthLevel(tree, k)) ` ` `  `# This code is contributed by ` `# Shubham Singh(SHUBHAMSINGH10) `

## C#

 `// C# implementation to find sum of  ` `// digits of elements at k-th level  ` ` `  `using` `System; ` `class` `GfG {  ` ` `  `// Function to find sum of digits  ` `// of elements at k-th level  ` `static` `int` `sumAtKthLevel(``string` `tree, ``int` `k)  ` `{  ` `    ``int` `level = -1;  ` `    ``int` `sum = 0; ``// Initialize result  ` `    ``int` `n = tree.Length;  ` ` `  `    ``for` `(``int` `i = 0; i < n; i++)  ` `    ``{  ` `        ``// increasing level number  ` `        ``if` `(tree[i] == ``'('``)  ` `            ``level++;  ` ` `  `        ``// decreasing level number  ` `        ``else` `if` `(tree[i] == ``')'``)  ` `            ``level--;  ` ` `  `        ``else` `        ``{  ` `            ``// check if current level is  ` `            ``// the desired level or not  ` `            ``if` `(level == k)  ` `                ``sum += (tree[i]-``'0'``);  ` `        ``}  ` `    ``}  ` ` `  `    ``// required sum  ` `    ``return` `sum;  ` `}  ` ` `  `// Driver code ` `public` `static` `void` `Main()  ` `{  ` `    ``string` `tree = ``"(0(5(6()())(4()(9()())))(7(1()())(3()())))"``;  ` `    ``int` `k = 2;  ` `    ``Console.Write(sumAtKthLevel(tree, k));  ` `} ` `}  ` ` `  `// This code is contributed by Ita_c `

/div>

Output:

```14
```

Time Complexity: O(n)

Tree Tree