Grokking 75: Top Coding Interview Questions
Vote

0% completed

​

Path with Maximum Sum (hard)

Problem Statement

Find the path with the maximum sum in a given binary tree. Write a function that returns the maximum sum.

A path can be defined as a sequence of nodes between any two nodes and doesn’t necessarily pass through the root. The path must contain at least one node.

Constraints:

  • The number of nodes in the tree is in the range [1, 3 * 10<sup>4</sup>].
  • -1000 <= Node.val <= 1000

Try it yourself

Try solving this question here:

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Athanasios Petsas

· 4 years ago

what if all of the numbers in the nodes are negative?

Show 3 replies
L

lejafilip

· 2 years ago

  1. Keep in mind that you need to check path every node. Not every leaf as it was in before problem.
  2. Consider if you need to sum a negative path.
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

lass Solution:
  
  def dfs(self, node):
    if not node:
      return 0

    left = self.dfs(node.left)
    right = self.dfs(node.right)

    path = 0 
    if right > 0 and left < 0:
      path = right + node.val
    elif left > 0 and right < 0:
      path = left + node.val
    else: 
      path = left + right + node.val

    self.max_path = max(self.max_path, path)

    return max(left, right) + node.val

  def findMaximumPathSum(self, root):
    self.max_path = root.val
    self.dfs(root)
    return self.max_path
Gustavo Alves

Gustavo Alves

· 9 months ago

A path should contain at least two nodes, therefore the example below is wrong:

Your Input: [1, -2, -3] Output: -1 Expected: 1