Maximum Sum Path in a Binary Tree

Question

I am trying to solve this question: https://leetcode.com/problems/binary-tree-maximum-path-sum/description/.

To find maximum sum path is like finding maximum path between any two nodes, that path may or may not pass through the root; except that with max sum path we want to track sum instead of path length.

So, I adapted the diameter of a binary tree's solution to find the maximum sum path.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:

    def height(self, root):
        if root==None:
            return 0

        lh = self.height(root.left)
        rh = self.height(root.right)

        return max(root.val+lh, root.val+rh)

    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root==None:
            return 0

        lh = self.height(root.left)
        rh = self.height(root.right)

        ld =  self.maxPathSum(root.left)
        rd =  self.maxPathSum(root.right)

        return max(lh+rh+root.val, root.val+ max(ld , rd))

My solution is passing 40 test cases before failing.

I am stuck at trying to figure out the correct solution. My solution works for finding the diameter, I just added sum in the return values.

Why is this not a generic solution as i am clearly traversing all the paths and taking appropriate max in return values.

Thanks for your help.

user3386109 · Accepted Answer · 2018-03-02 08:59:57Z

2

The problem is this line

return max(lh+rh+root.val, root.val+ max(ld , rd))

It should be

return max(lh+rh+root.val, max(ld , rd))

Note that the root node is not part of the path for ld and rd.

answered Mar 2, 2018 at 8:59

user3386109

35k7 gold badges52 silver badges69 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

mourinho Over a year ago

thanks, the code fails for just a tree with one node: -3. the code returns 0.

user3386109 Over a year ago

@mourinho I didn't realize there could be negative values in the tree. Dealing with negative values makes the problem a whole lot harder. For example, when computing the height, it might be advantageous to stop before you reach a leaf node. Which means that you need to consider the path from every node to every other node. Your algorithm is only checking paths from a root to two leaf nodes.

mourinho Over a year ago

this is happening because I am not initiazlizing the minimum anywhere so max (-3, 0) is giving 0. Don't really know how to do that in recursion... the current solution, your answer is passing 60 test cases...so I think logic is fine..

user3386109 Over a year ago

Consider a tree where all the values are negative, except for two positive nodes that happen to be connected to each other. The best path is going to be the path between those two nodes.

Collectives™ on Stack Overflow

Maximum Sum Path in a Binary Tree

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related