Count subtrees that sum up to a given value x only using single recursive function | c # program to find if there is a subtree with given sum ; 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 Code ; binary tree creation 5 / \ - 10 3 / \ / \ 9 8 - 4 7
using System ; public class GFG { public class Node { public int data ; public Node left , right ; } public class INT { public int v ; public INT ( int a ) { v = a ; } } public static Node getNode ( int data ) { Node newNode = new Node ( ) ; newNode . data = data ; newNode . left = newNode . right = null ; return newNode ; } public static int countSubtreesWithSumX ( Node root , INT count , int x ) { if ( root == null ) { 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 . v ++ ; } return sum ; } public static int countSubtreesWithSumXUtil ( Node root , int x ) { if ( root == null ) { return 0 ; } INT count = new INT ( 0 ) ; int ls = countSubtreesWithSumX ( root . left , count , x ) ; int rs = countSubtreesWithSumX ( root . right , count , x ) ; if ( ( ls + rs + root . data ) == x ) { count . v ++ ; } return count . v ; } public static void Main ( string [ ] args ) { 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 ) ) ; } }