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














































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



#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
//description :: Given an integer %u2018K%u2019 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
 
TREE

//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
//logic :
//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

More Articles of Priya Vijayvargiya:

Name Views Likes
Sum of nodes at k-th level in a tree represented as string 243 14

Comments