Find the maximum sum leaf to root path in a Binary Tree | A tree node structure ; A utility function that prints all nodes on the path from root to target_leaf ; base case ; return True if this node is the target_leaf or target leaf is present in one of its descendants ; This function Sets the target_leaf_ref to refer the leaf node of the maximum path sum . Also , returns the max_sum using max_sum_ref ; Update current sum to hold sum of nodes on path from root to this node ; If this is a leaf node and path to this node has maximum sum so far , then make this node target_leaf ; If this is not a leaf node , then recur down to find the target_leaf ; Returns the maximum sum and prints the nodes on max sum path ; base case ; find the target leaf and maximum sum ; print the path from root to the target leaf ; return maximum sum ; Utility function to create a new Binary Tree node ; Driver function to test above functions
class node : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . data = 0 NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def printPath ( root , target_leaf ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( root == target_leaf or printPath ( root . left , target_leaf ) or printPath ( root . right , target_leaf ) ) : NEW_LINE INDENT print ( root . data , end = " ▁ " ) NEW_LINE return True NEW_LINE DEDENT return False NEW_LINE DEDENT max_sum_ref = 0 NEW_LINE target_leaf_ref = None NEW_LINE def getTargetLeaf ( Node , curr_sum ) : NEW_LINE INDENT global max_sum_ref NEW_LINE global target_leaf_ref NEW_LINE if ( Node == None ) : NEW_LINE INDENT return NEW_LINE DEDENT curr_sum = curr_sum + Node . data NEW_LINE if ( Node . left == None and Node . right == None ) : NEW_LINE INDENT if ( curr_sum > max_sum_ref ) : NEW_LINE INDENT max_sum_ref = curr_sum NEW_LINE target_leaf_ref = Node NEW_LINE DEDENT DEDENT getTargetLeaf ( Node . left , curr_sum ) NEW_LINE getTargetLeaf ( Node . right , curr_sum ) NEW_LINE DEDENT def maxSumPath ( Node ) : NEW_LINE INDENT global max_sum_ref NEW_LINE global target_leaf_ref NEW_LINE if ( Node == None ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT target_leaf_ref = None NEW_LINE max_sum_ref = - 32676 NEW_LINE getTargetLeaf ( Node , 0 ) NEW_LINE printPath ( Node , target_leaf_ref ) ; NEW_LINE return max_sum_ref ; NEW_LINE DEDENT def newNode ( data ) : NEW_LINE INDENT temp = node ( ) ; NEW_LINE temp . data = data ; NEW_LINE temp . left = None ; NEW_LINE temp . right = None ; NEW_LINE return temp ; NEW_LINE DEDENT root = None ; NEW_LINE root = newNode ( 10 ) ; NEW_LINE root . left = newNode ( - 2 ) ; NEW_LINE root . right = newNode ( 7 ) ; NEW_LINE root . left . left = newNode ( 8 ) ; NEW_LINE root . left . right = newNode ( - 4 ) ; NEW_LINE print ( " Following ▁ are ▁ the ▁ nodes ▁ on ▁ the ▁ maximum ▁ sum ▁ path ▁ " ) ; NEW_LINE sum = maxSumPath ( root ) ; NEW_LINE print (   " Sum of the nodes is   " , sum ) ; NEW_LINE