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,
- 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)