# Count subtrees that sum up to a given value x only using single recursive function

Hello Everyone,

Given a binary tree containing n nodes. The problem is to count subtrees having total node’s data sum equal to a given value using only single recursive functions.

Approach:

countSubtreesWithSumX(root, count, x) if !root then return 0 ls = countSubtreesWithSumX(root->left, count, x) rs = countSubtreesWithSumX(root->right, count, x) sum = ls + rs + root->data if sum == x then count++ return sum countSubtreesWithSumXUtil(root, x) if !root then return 0 Initialize count = 0 ls = countSubtreesWithSumX(root->left, count, x) rs = countSubtreesWithSumX(root->right, count, x) if (ls + rs + root->data) == x count++ return count

`// C++ implementation to count subtress that`

`// sum up to a given value x`

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

`using` `namespace` `std;`

`// structure of a node of binary tree`

`struct` `Node {`

` ` `int` `data;`

` ` `Node *left, *right;`

`};`

`// function to get a new node`

`Node* getNode(` `int` `data)`

`{`

` ` `// allocate space`

` ` `Node* newNode = (Node*)` `malloc` `(` `sizeof` `(Node));`

` ` `// put in the data`

` ` `newNode->data = data;`

` ` `newNode->left = newNode->right = NULL;`

` ` `return` `newNode;`

`}`

`// function to count subtress that`

`// sum up to a given value x`

`int` `countSubtreesWithSumX(Node* root,`

` ` `int` `& count, ` `int` `x)`

`{`

` ` `// if tree is empty`

` ` `if` `(!root)`

` ` `return` `0;`

` ` `// sum of nodes in the left subtree`

` ` `int` `ls = countSubtreesWithSumX(root->left, count, x);`

` ` `// sum of nodes in the right subtree`

` ` `int` `rs = countSubtreesWithSumX(root->right, count, x);`

` ` `// sum of nodes in the subtree rooted`

` ` `// with 'root->data'`

` ` `int` `sum = ls + rs + root->data;`

` ` `// if true`

` ` `if` `(sum == x)`

` ` `count++;`

` ` `// return subtree's nodes sum`

` ` `return` `sum;`

`}`

`// utility function to count subtress that`

`// sum up to a given value x`

`int` `countSubtreesWithSumXUtil(Node* root, ` `int` `x)`

`{`

` ` `// if tree is empty`

` ` `if` `(!root)`

` ` `return` `0;`

` ` `int` `count = 0;`

` ` `// sum of nodes in the left subtree`

` ` `int` `ls = countSubtreesWithSumX(root->left, count, x);`

` ` `// sum of nodes in the right subtree`

` ` `int` `rs = countSubtreesWithSumX(root->right, count, x);`

` ` `// if tree's nodes sum == x`

` ` `if` `((ls + rs + root->data) == x)`

` ` `count++;`

` ` `// required count of subtrees`

` ` `return` `count;`

`}`

`// Driver program to test above`

`int` `main()`

`{`

` ` `/* binary tree creation `

` ` `5`

` ` `/ \ `

` ` `-10 3`

` ` `/ \ / \`

` ` `9 8 -4 7`

` ` `*/`

` ` `Node* root = getNode(5);`

` ` `root->left = getNode(-10);`

` ` `root->right = getNode(3);`

` ` `root->left->left = getNode(9);`

` ` `root->left->right = getNode(8);`

` ` `root->right->left = getNode(-4);`

` ` `root->right->right = getNode(7);`

` ` `int` `x = 7;`

` ` `cout << ` `"Count = "`

` ` `<< countSubtreesWithSumXUtil(root, x);`

` ` `return` `0;`

`}`

Output:

Count = 2

Time Complexity: O(n).