Count subtrees that sum up to a given value x only using single recursive function | C ++ implementation to count subtress that sum up to a given value x ; structure of a node of binary tree ; function to get a new node ; allocate space ; put in the data ; function to count subtress that sum up to a given value x ; if tree is empty ; sum of nodes in the left subtree ; sum of nodes in the right subtree ; sum of nodes in the subtree rooted with ' root - > data ' ; if true ; return subtree 's nodes sum ; utility function to count subtress that sum up to a given value x ; if tree is empty ; sum of nodes in the left subtree ; sum of nodes in the right subtree ; if tree 's nodes sum == x ; required count of subtrees ; Driver program to test above ; binary tree creation 5 / \ - 10 3 / \ / \ 9 8 - 4 7
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * left , * right ; } ; Node * getNode ( int data ) { Node * newNode = ( Node * ) malloc ( sizeof ( Node ) ) ; newNode -> data = data ; newNode -> left = newNode -> right = NULL ; return newNode ; } int countSubtreesWithSumX ( Node * root , int & count , int x ) { if ( ! root ) return 0 ; int ls = countSubtreesWithSumX ( root -> left , count , x ) ; int rs = countSubtreesWithSumX ( root -> right , count , x ) ; int sum = ls + rs + root -> data ; if ( sum == x ) count ++ ; return sum ; } int countSubtreesWithSumXUtil ( Node * root , int x ) { if ( ! root ) return 0 ; int count = 0 ; int ls = countSubtreesWithSumX ( root -> left , count , x ) ; int rs = countSubtreesWithSumX ( root -> right , count , x ) ; if ( ( ls + rs + root -> data ) == x ) count ++ ; return count ; } int main ( ) { 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 ; }