Count subtrees that sum up to a given value x only using single recursive function | Structure of a node of binary tree ; Function to get a new node ; Allocate space ; Utility function to count subtress that sum up to a given value x ; Driver code ; binary tree creation 5 / \ - 10 3 / \ / \ 9 8 - 4 7
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def getNode ( data ) : NEW_LINE INDENT newNode = Node ( data ) NEW_LINE return newNode NEW_LINE DEDENT count = 0 NEW_LINE ptr = None NEW_LINE def countSubtreesWithSumXUtil ( root , x ) : NEW_LINE INDENT global count , ptr NEW_LINE l = 0 NEW_LINE r = 0 NEW_LINE if ( root == None ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT l += countSubtreesWithSumXUtil ( root . left , x ) NEW_LINE r += countSubtreesWithSumXUtil ( root . right , x ) NEW_LINE if ( l + r + root . data == x ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT if ( ptr != root ) : NEW_LINE INDENT return l + root . data + r NEW_LINE DEDENT return count 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 ptr = root NEW_LINE print ( " Count ▁ = ▁ " + str ( countSubtreesWithSumXUtil ( root , x ) ) ) NEW_LINE DEDENT