/*Take input of a generic tree using buildtree() function and also take input K the level at which we need to find the sum.
Input Format
Take a generic tree input where you are first given the data of the node and then its no of children.
The input is of preorder form and it is assured that the no of children will not exceed 2.
The input of the tree is followed by a single integer K.
Constraints
1 <= Nodes in tree <=1000
1<K<10
Output Format
A single line containing the sum at level K.
Sample Input
1 2
2 2
3 0
4 0
5 2
6 0
7 0
2
Sample Output
20
Explanation
Here the tree looks like
1 Level 0
/ \
2 5 Level 1
/ \ / \
3 4 6 7 Level 2
Sum at Level 2 = 3 + 4 + 6 + 7 = 20
*/
#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data;
nodeleft;
noderight;
node(int d){
data=d;
left=NULL;
right=NULL;
}
};
node* buildTree(){
int d, num;
cin>>d>>num;
if(num==0){
noderoot=new node(d);
root->left=NULL;
root->right=NULL;
return root;
}
else if(num==1){
noderoot= new node(d);
root->left=buildTree();
root->left=NULL;
return root;
}
else{
noderoot=new node(d);
root->left=buildTree();
root->right=buildTree();
return root;
}
}
void print(noderoot){
if(root==NULL){
return ;
}
cout<data<<" ";
print(root->left);
print(root->right);
return ;
}
int height(node*root){
if(root==NULL){
return 0;
}
int hl=height(root->left)+hl;
int hr=height(root->right)+hr;
return max(hl,hr)+1;
}
void sumAtKthLevel(node*root,int k,int& sum){
if(root==NULL || k==0){
return ;
}
if(k==1){
sum=sum+root->data;
return ;
}
sumAtKthLevel(root->left,k-1,sum);
sumAtKthLevel(root->right,k-1,sum);
return ;
}
int main(){
node*root=buildTree();
int k;
cin>>k;
int sum=0;
sumAtKthLevel(root,k+1,sum);
cout<<sum<<endl;
return 0;
}