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
Why this is a Tree Depth First Search problem
| What the question says | The signal it matches |
|---|---|
| "sequence of nodes between any two nodes" | the question is about a path |
| "doesn't necessarily pass through the root" | the answer for a node depends on the answers from its subtrees |
This is the combine two subtrees at each node variant: Tree Diameter with the node count replaced by a sum.
The closest alternative. There is none, but Tree Diameter is the problem to reuse. Each node still returns its best upward path and separately records its best bending path.
The sum changes two things, and both come from the constraints. Values can be negative, since "-1000 <= Node.val <= 1000". A child whose best path sums below zero should contribute nothing, so its report is replaced by zero. And "The path must contain at least one node", so the answer starts at a real node's value rather than at zero. Start it at zero and a tree of all negative values returns the wrong answer.
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:
Code
Here is the code for this algorithm:
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).