Please explain the concept of recursion in this question

#1

Ques:-Count subtrees that sum up to a given value x only using single recursive function

#2

Hey @manikjindal49

int recurscive(root,x,&count)
… if root is null return 0
… cursum=root->data +recursive(root->left) +recursive(root->right)
… if cursum==x then count+=1
… return cursum

This should work for the above question.
If u don’t understand something in this then let me know.

#3

I also have used this method only but not getting the result

#4

static int count=0; if(root==NULL){ return 0; } int ls=0,rs=0; ls+=countSubtreesWithSumX(root->left,X); rs+=countSubtreesWithSumX(root->right,X); if(ls+rs+root->data==X){ count++; } return count;

#5

hello @manikjindal49

if we r on root then
countSubtreewithSum(root->left,X) return sum of the all the nodes of subtree root->left.

similarly
countSubtreewithSum(root->right,X) return sum of the all the nodes of subtree root->right.

then we are adding these returned sum with data of current root to check whether subtree starting from root has sum X or not . if it is then we incrementing count.

we have made our count as static because we want to initilaise count with only 0nce.

#6

u have to return ls+rs+root->data

#7

u have to return ls+rs+root->data .I still cannot understand why we have to return this

#8

this is sum of all nodes present in ur current root, we are returning this to its parent node .
parent node use this sum to compute its total subtree sum

#9

What u still didn’t understood?

#10

i have sent you my new modified code in chat can you please check it once

#11

static int count=0;
static Node* ptr=root;
if(root==NULL){
return 0;
}
int ls=0,rs=0;
ls+=countSubtreesWithSumX(root->left,X);
rs+=countSubtreesWithSumX(root->right,X);
if(ls+rs+root->data==X){
count++;
}
if(ptr!=root)
return ls+root->data+rs;
return count;

This looks good ,but what u want me to expalin in this exactly .

Basically question was to count subtrees having sum x
So by recursion we just calculate sum of subtrees and calculation includes to increment the count of subtree if its sum is x

#12

I am not gettig answer with the code My test case is failing 4 0 1 N 2 0 -2 N -4 -1 -3 N 0 -3 -5

#13

Please share the question link as well as your code in some IDE

#14

Ques :-Count Number of SubTrees having given Sum Geeks for geeks practice and code i have given in above comment pls check this

#15

Hey @manikjindal49
solve it without static
there are multple testcases in same input in the background and hence its giving error because of static.
Yoou can try this as custom input and it will give u correct answer.

#16

If we remove the static then it is showing the answer as 0 for all test cases and i also tried making another function in which count is one of parameter but then also it is showing answer as 0;

#17

Share this solution …

#18

Nothing new just pass count as one of the parameters nothing new code was written can you please provide me the solution also if possible according to you

#19

Pass it by reference and u are good to go
You can give me your code and I will rectify it .

#20

static int count=0; static Node* ptr=root; if(root==NULL){ return 0; } int ls=0,rs=0; ls+=countSubtreesWithSumX(root->left,X); rs+=countSubtreesWithSumX(root->right,X); if(ls+rs+root->data==X){ count++; } if(ptr!=root) return ls+root->data+rs; return count;