Solution: Problem Challenge 2: Path with Maximum Sum

Blind 75

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. The only difference will be to ignore the paths with negative sums. Since we need to find the overall maximum sum, we should ignore any path which has an overall negative sum.

Here is the visual representation of the algorithm:

Path with Max Sum

Code

Here is the code for this algorithm:

Python3

Time Complexity

The time complexity of the above algorithm is $O(N)$ , where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once.

Space Complexity

The space complexity of the above algorithm will be $O(N)$ in the worst case. This space will be used to store the recursion stack. The worst case will happen when the given tree is a linked list (i.e., every node has only one child).