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