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

Hello Everyone,

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

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

Now,

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++ implementation to find sum of`

`// digits of elements at k-th level`

`#include <bits/stdc++.h>`

`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<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 program to test above`

`int` `main()`

`{`

` ` `string tree = ` `"(0(5(6()())(4()(9()())))(7(1()())(3()())))"` `;`

` ` `int` `k = 2;`

` ` `cout << sumAtKthLevel(tree, k);`

` ` `return` `0;`

`}`

Output:

14

Time Complexity: O(n)

Recursive Method: The idea is to treat the string as tree without actually creating one, and simply traverse the string recursively in Postorder Fashion and consider nodes which are at level k only.

Following is the implementation of the same:

`// C++ implementation to find sum of`

`// digits of elements at k-th level`

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

`// Recursive Function to find sum of digits`

`// of elements at k-th level`

`int` `sumAtKthLevel(string tree, ` `int` `k,` `int` `&i,` `int` `level)`

`{`

` `

` ` `if` `(tree[i++]==` `'('` `)`

` ` `{`

` `

` ` `// if subtree is null, just like if root == NULL`

` ` `if` `(tree[i] == ` `')'` `)`

` ` `return` `0; `

` `

` ` `int` `sum=0;`

` `

` ` `// Consider only level k node to be part of the sum`

` ` `if` `(level == k)`

` ` `sum = tree[i]-` `'0'` `;`

` `

` ` `// Recur for Left Subtree`

` ` `int` `leftsum = sumAtKthLevel(tree,k,++i,level+1);`

` `

` ` `// Recur for Right Subtree`

` ` `int` `rightsum = sumAtKthLevel(tree,k,++i,level+1);`

` `

` ` `// Taking care of ')' after left and right subtree`

` ` `++i;`

` ` `return` `sum+leftsum+rightsum; `

` ` `}`

`}`

`// Driver program to test above`

`int` `main()`

`{`

` ` `string tree = ` `"(0(5(6()())(4()(9()())))(7(1()())(3()())))"` `;`

` ` `int` `k = 2;`

` ` `int` `i=0;`

` ` `cout << sumAtKthLevel(tree, k,i,0);`

` ` `return` `0;`

`}`

Output :

14

Time Complexity: O(n)