Binary Tree Maximum Path Sum
Explore how to calculate the maximum sum of any path within a binary tree, including partial or full paths not necessarily including the root. Learn to implement a recursive function that evaluates node contributions, decides whether to continue or start new paths, and updates the maximum sum efficiently with O(n) time complexity.
We'll cover the following...
Statement
Given the root of a binary tree, return the maximum sum of any non-empty path.
A path in a binary tree is defined as:
“A sequence of nodes such that each pair of adjacent nodes must have an edge connecting them. A node can only be included in a path at most once. Moreover, including the root in the path is not compulsory.”
We can calculate the path sum by adding up all nodes’ values in the path. To solve this problem, we’ll calculate the maximum path sum given the root of a binary tree so that there won’t be any greater path than it in the tree.
Example
For the following tree, the maximum path sum is:
, and the total sum = ...