Implement an algorithm to populate a variable `count`

which represents number of subsets in a binary tree with same sum of their data as the input sum.
A subset is defined as a sub-tree with leave nodes.

1 / \ 1 1 / \ / \ 1 1 1 1 Input Sum : 3 Output : 2

Need a **hand?** Try out these hints, one at a time.

The key here is to keep

`incrementing`

the `count`

in case the sum of the data of all the nodes of a subtree is equal to the input sum.The sum of the sub nodes at each node can be found through recursive approach.
The key here is to **Recursively** find the `sum`

of each nodes, with the `logic`

to increment `count`

at an appropriate step.

1. If the `root node`

is `null`

, then `return 0`

.

2. Calculate the `sum`

at the `node`

and store it in the temp variable i.e. `tempSum = sum(rootNode.left, inputSum) + rootNode.data + sum(rootNode.right, inputSum)`

3. If `tempSum`

is equal to the `input sum`

then increment the `count`

variable.

At the end of `recursion`

, `count`

variable will give the number of sub trees with the sum of nodes same as the input sum.

/* Populate this variable to represent number of subsets with summation of data as input sum */ int count = 0; int sum(Node rootNode, int inputSum) { }

**C**

**Java**

**Python**