Count subtrees that sum up to a given value x only using single recursive function | class to get a new node ; 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
class getNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = self . right = None NEW_LINE DEDENT DEDENT def countSubtreesWithSumX ( root , count , x ) : NEW_LINE INDENT if ( not root ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT ls = countSubtreesWithSumX ( root . left , count , x ) NEW_LINE rs = countSubtreesWithSumX ( root . right , count , x ) NEW_LINE Sum = ls + rs + root . data NEW_LINE if ( Sum == x ) : NEW_LINE INDENT count [ 0 ] += 1 NEW_LINE DEDENT return Sum NEW_LINE DEDENT def countSubtreesWithSumXUtil ( root , x ) : NEW_LINE INDENT if ( not root ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT count = [ 0 ] NEW_LINE ls = countSubtreesWithSumX ( root . left , count , x ) NEW_LINE rs = countSubtreesWithSumX ( root . right , count , x ) NEW_LINE if ( ( ls + rs + root . data ) == x ) : NEW_LINE INDENT count [ 0 ] += 1 NEW_LINE DEDENT return count [ 0 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = getNode ( 5 ) NEW_LINE root . left = getNode ( - 10 ) NEW_LINE root . right = getNode ( 3 ) NEW_LINE root . left . left = getNode ( 9 ) NEW_LINE root . left . right = getNode ( 8 ) NEW_LINE root . right . left = getNode ( - 4 ) NEW_LINE root . right . right = getNode ( 7 ) NEW_LINE x = 7 NEW_LINE print ( " Count ▁ = " , countSubtreesWithSumXUtil ( root , x ) ) NEW_LINE DEDENT