Count subtrees that sum up to a given value x

Given a binary tree containing n nodes. The problem is to count subtress having total node’s data sum equal to a given value x.

Examples:

```Input :
5
/
-10     3
/     /
9    8 -4   7

x = 7

Output : 2
There are 2 subtrees with sum 7.

1st one is leaf node:
7.

2nd one is:

-10
/
9     8

```

Algorithm:

```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++

 `// C++ implementation to count subtress that ` `// sum up to a given value x ` `#include ` ` `  `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; ` `} `

Java

 `// Java program to find if  ` `// there is a subtree with  ` `// given sum  ` `import` `java.util.*;  ` `class` `GFG ` `{ ` ` `  `// structure of a node  ` `// of binary tree  ` `static` `class` `Node ` `{  ` `    ``int` `data;  ` `    ``Node left, right;  ` `} ` ` `  `static` `class` `INT ` `{ ` `    ``int` `v; ` `    ``INT(``int` `a) ` `    ``{ ` `        ``v = a; ` `    ``} ` `} ` ` `  `// function to get a new node  ` `static` `Node getNode(``int` `data)  ` `{  ` `    ``// allocate space  ` `    ``Node newNode = ``new` `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  ` `static` `int` `countSubtreesWithSumX(Node root,  ` `                          ``INT count, ``int` `x)  ` `{  ` `    ``// if tree is empty  ` `    ``if` `(root == ``null``)  ` `        ``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.v++;  ` ` `  `    ``// return subtree's nodes sum  ` `    ``return` `sum;  ` `}  ` ` `  `// utility function to  ` `// count subtress that  ` `// sum up to a given value x  ` `static` `int` `countSubtreesWithSumXUtil(Node root,  ` `                                     ``int` `x)  ` `{  ` `    ``// if tree is empty  ` `    ``if` `(root == ``null``)  ` `        ``return` `0``;  ` ` `  `    ``INT count = ``new` `INT(``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.v++;  ` ` `  `    ``// required count of subtrees  ` `    ``return` `count.v;  ` `}  ` ` `  `// Driver Code ` `public` `static` `void` `main(String args[]) ` `{  ` `    ``/* 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``;  ` ` `  `    ``System.out.println(``"Count = "` `+  ` `           ``countSubtreesWithSumXUtil(root, x));  ` `}  ` `} ` ` `  `// This code is contributed  ` `// by Arnab Kundu `

Python3

# Python3 implementation to count subtress
# that Sum up to a given value x

# class to get a new node
class getNode:
def __init__(self, data):

# put in the data
self.data = data
self.left = self.right = None

# function to count subtress that
# Sum up to a given value x
def countSubtreesWithSumX(root, count, x):

# if tree is empty
if (not root):
return 0

# Sum of nodes in the left subtree
ls = countSubtreesWithSumX(root.left,
count, x)

# Sum of nodes in the right subtree
rs = countSubtreesWithSumX(root.right,
count, x)

# Sum of nodes in the subtree
# rooted with ‘root.data’
Sum = ls + rs + root.data

# if true
if (Sum == x):
count[0] += 1

# return subtree’s nodes Sum
return Sum

# utility function to count subtress
# that Sum up to a given value x
def countSubtreesWithSumXUtil(root, x):

# if tree is empty
if (not root):
return 0

count = [0]

# Sum of nodes in the left subtree
ls = countSubtreesWithSumX(root.left,
count, x)

# Sum of nodes in the right subtree
rs = countSubtreesWithSumX(root.right,
count, x)

# if tree’s nodes Sum == x
if ((ls + rs + root.data) == x):
count[0] += 1

# required count of subtrees
return count[0]

# Driver Code
if __name__ == ‘__main__’:

# binary tree creation
# 5
# /
# -10 3
# / /
# 9 8 -4 7
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)

x = 7

print(“Count =”,
countSubtreesWithSumXUtil(root, x))

# This code is contributed by PranchalK

C#

 `using` `System; ` ` `  `// c# program to find if  ` `// there is a subtree with  ` `// given sum  ` `public` `class` `GFG ` `{ ` ` `  `// structure of a node  ` `// of binary tree  ` `public` `class` `Node ` `{ ` `    ``public` `int` `data; ` `    ``public` `Node left, right; ` `} ` ` `  `public` `class` `INT ` `{ ` `    ``public` `int` `v; ` `    ``public` `INT(``int` `a) ` `    ``{ ` `        ``v = a; ` `    ``} ` `} ` ` `  `// function to get a new node  ` `public` `static` `Node getNode(``int` `data) ` `{ ` `    ``// allocate space  ` `    ``Node newNode = ``new` `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  ` `public` `static` `int` `countSubtreesWithSumX(Node root,  ` `                                    ``INT count, ``int` `x) ` `{ ` `    ``// if tree is empty  ` `    ``if` `(root == ``null``) ` `    ``{ ` `        ``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.v++; ` `    ``} ` ` `  `    ``// return subtree's nodes sum  ` `    ``return` `sum; ` `} ` ` `  `// utility function to  ` `// count subtress that  ` `// sum up to a given value x  ` `public` `static` `int` `countSubtreesWithSumXUtil(Node root, ``int` `x) ` `{ ` `    ``// if tree is empty  ` `    ``if` `(root == ``null``) ` `    ``{ ` `        ``return` `0; ` `    ``} ` ` `  `    ``INT count = ``new` `INT(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.v++; ` `    ``} ` ` `  `    ``// required count of subtrees  ` `    ``return` `count.v; ` `} ` ` `  `// Driver Code  ` `public` `static` `void` `Main(``string``[] args) ` `{ ` `    ``/* 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; ` ` `  `    ``Console.WriteLine(``"Count = "` `+ countSubtreesWithSumXUtil(root, x)); ` `} ` `} ` ` `  `// This code is contributed by Shrikant13 `

Output:

```Count = 2
```

Time Complexity: O(n).