Find the maximum path sum between two leaves of a binary tree | Python program to find maximumpath sum between two leaves of a binary tree ; A binary tree node ; Utility function to find maximum sum between anytwo leaves . This function calculates two values : 1 ) Maximum path sum between two leaves which are stored in res2 ) The maximum root to leaf path sum which is returned If one side of root is empty , then it returns INT_MIN ; Base Case ; Find maximumsum in left and righ subtree . Also find maximum root to leaf sums in left and righ subtrees ans store them in ls and rs ; If both left and right children exist ; update result if needed ; Return maximum possible value for root being on one side ; If any of the two children is empty , return root sum for root being on one side ; The main function which returns sum of the maximum sum path betwee ntwo leaves . THis function mainly uses maxPathSumUtil ( ) ; Driver program to test above function
INT_MIN = - 2 ** 32 NEW_LINE 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 maxPathSumUtil ( root , res ) : NEW_LINE INDENT if root is None : NEW_LINE INDENT return 0 NEW_LINE DEDENT ls = maxPathSumUtil ( root . left , res ) NEW_LINE rs = maxPathSumUtil ( root . right , res ) NEW_LINE if root . left is not None and root . right is not None : NEW_LINE INDENT res [ 0 ] = max ( res [ 0 ] , ls + rs + root . data ) NEW_LINE return max ( ls , rs ) + root . data NEW_LINE DEDENT if root . left is None : NEW_LINE INDENT return rs + root . data NEW_LINE DEDENT else : NEW_LINE INDENT return ls + root . data NEW_LINE DEDENT DEDENT def maxPathSum ( root ) : NEW_LINE INDENT res = [ INT_MIN ] NEW_LINE maxPathSumUtil ( root , res ) NEW_LINE return res [ 0 ] NEW_LINE DEDENT root = Node ( - 15 ) NEW_LINE root . left = Node ( 5 ) NEW_LINE root . right = Node ( 6 ) NEW_LINE root . left . left = Node ( - 8 ) NEW_LINE root . left . right = Node ( 1 ) NEW_LINE root . left . left . left = Node ( 2 ) NEW_LINE root . left . left . right = Node ( 6 ) NEW_LINE root . right . left = Node ( 3 ) NEW_LINE root . right . right = Node ( 9 ) NEW_LINE root . right . right . right = Node ( 0 ) NEW_LINE root . right . right . right . left = Node ( 4 ) NEW_LINE root . right . right . right . right = Node ( - 1 ) NEW_LINE root . right . right . right . right . left = Node ( 10 ) NEW_LINE print " Max ▁ pathSum ▁ of ▁ the ▁ given ▁ binary ▁ tree ▁ is " , maxPathSum ( root ) NEW_LINE