Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Problem Challenge 2: Path with Maximum Sum

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

Solution

This problem follows the Binary Tree Path Sum pattern and shares the algorithmic logic with Tree Diameter. We can follow the same DFS approach

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Athanasios Petsas

· 5 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