Binary Tree Subsets with Same Sum

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.

Quick hint to get things rolling

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.

Final hint! You should be able to code the problem on viewing this.

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


}

This Coding Interview Question is available with an answer in the following programming languages :

Java

Python

Binary Tree Subsets with Same Sum

Quick hint to get things rolling

Final hint! You should be able to code the problem on viewing this.

The interview prep tool you'll fall in love with!

This Coding Interview Question is available with an answer in the following programming languages :