Find if there is a pair in root to a leaf path with sum equals to root 's data | utility that allocates a new node with the given data and None left and right pointers . ; Function to prroot to leaf path which satisfies the condition ; Base condition ; Check if current node makes a pair with any of the existing elements in set . ; Insert current node in set ; If result returned by either left or right child is True , return True . ; Remove current node from hash table ; A wrapper over printPathUtil ( ) ; create an empty hash table ; Recursively check in left and right subtrees . ; Driver Code
class newnode : 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 printPathUtil ( node , s , root_data ) : NEW_LINE INDENT if ( node == None ) : NEW_LINE INDENT return False NEW_LINE DEDENT rem = root_data - node . data NEW_LINE if rem in s : NEW_LINE INDENT return True NEW_LINE DEDENT s . add ( node . data ) NEW_LINE res = printPathUtil ( node . left , s , root_data ) or printPathUtil ( node . right , s , root_data ) NEW_LINE s . remove ( node . data ) NEW_LINE return res NEW_LINE DEDENT def isPathSum ( root ) : NEW_LINE INDENT s = set ( ) NEW_LINE return printPathUtil ( root . left , s , root . data ) or printPathUtil ( root . right , s , root . data ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newnode ( 8 ) NEW_LINE root . left = newnode ( 5 ) NEW_LINE root . right = newnode ( 4 ) NEW_LINE root . left . left = newnode ( 9 ) NEW_LINE root . left . right = newnode ( 7 ) NEW_LINE root . left . right . left = newnode ( 1 ) NEW_LINE root . left . right . right = newnode ( 12 ) NEW_LINE root . left . right . right . right = newnode ( 2 ) NEW_LINE root . right . right = newnode ( 11 ) NEW_LINE root . right . right . left = newnode ( 3 ) NEW_LINE print ( " Yes " ) if ( isPathSum ( root ) ) else print ( " No " ) NEW_LINE DEDENT