124. Binary Tree Maximum Path Sum

HardTreeDepth-First SearchDynamic ProgrammingBinary Tree

Problem Description

In this problem, we are given the root of a binary tree and need to find the maximum path sum from any sequence of nodes in the tree. Here, a path is defined as a sequence of nodes where consecutive nodes are connected by an edge, and a node can only be used once within a single path. The path sum is the total of the values of all nodes in that path. Notably, the path does not have to go through the root of the tree. Our goal is to calculate the maximum sum from all such possible paths in the tree.

Flowchart Walkthrough

Let's analyze the problem using the algorithm flowchart provided at the Flowchart. Here's a step-by-step traversal through the flowchart to decide the appropriate algorithm:

Is it a graph?

Yes: In this case, the binary tree can be considered a specific type of graph.

Is it a tree?

Yes: The structure specifically mentioned is a binary tree, which is a form of a tree.

At this point in the flowchart, we reach the node labeled "DFS" directly after confirming the structure is a tree. This implies that the Depth-First Search (DFS) algorithm is suitable for traversing or manipulating tree data structures, particularly for problems like the one described where we need to consider paths that traverse up and down through the tree structure to calculate maximum path sums. DFS is highly efficient for tree problems as it allows us to explore all possibilities from root through various branches to the leaves, and in this case, back up.

Conclusion: The binary tree structure suggests using DFS for effectively solving the problem of finding the maximum path sum. This method will help in exploring all potential paths efficiently to find the maximum sum.

Intuition

When dealing with trees, recursion is often a natural approach. Since we are looking for the maximum path sum, at every node we have a choice: include that node on a path extending left or right, or start a new path through that node. We can recursively find the maximum path sums going through the left child and the right child. However, when combining these sums at a node, we must realize that we cannot include both child paths since that would create a loop, not a valid path.

The solution's intuition hinges on realizing that for any node, the maximum sum wherein that node is the highest point (i.e., the 'root' of that path) is its value plus the maximum sums of its left and right subtrees. We only add the subtree sums if they are positive, since any path would only include a subtree if it contributed positively to the total sum.

We define the dfs function that does the following:

When the node is None, return 0 because an empty node contributes nothing to the path sum.
Recursively calculate the maximum path sum for the left and right subtrees. If the sum is negative, we reset it to 0, as described earlier.
Calculate the potential maximum path sum at the current node by adding the node's value to the maximum path sums from both subtrees. This represents the largest value that could be achieved when passing through that node and potentially including both left and right paths (but not combining them).
Update a global variable ans that tracks the overall maximum path sum found anywhere in the tree with this new potential maximum.
Finally, for the recursion to continue upwards, return the node's value plus the greater of the two maximum sums from the left or right subtree. This represents the best contribution that node can make towards a higher path.

The maxPathSum function initiates this recursive process, starting from the root, and returns the maximum path sum found.

Learn more about Tree, Depth-First Search, Dynamic Programming and Binary Tree patterns.

Solution Approach

The solution uses a Depth-First Search (DFS) algorithm to recursively traverse the binary tree and calculate the path sums. This approach ensures that every node is visited, and that the maximum path sums for the subtrees of each node are considered. Here are the steps and ideas involved:

The core function is dfs, which is a recursive function that takes a node of the tree as an argument and returns the maximum path sum obtained by including the current node and extending to either its left or right child (not both).
In the base case, if the current node is None, the function returns 0, meaning there is no contribution to the path sum.
When dfs is called on a non-null node, it first recursively calculates the maximum path sums of the left and right subtrees with left = max(0, dfs(root.left)) and right = max(0, dfs(root.right)). The max(0, ...) pattern is used to ignore negative path sums since including a negative path would decrease the overall sum, which is not optimal.
After obtaining the maximum non-negative path sums from the left and right subtrees, it calculates the maximum path sum that includes the current node and both children: root.val + left + right. This is not the value returned by the function because a path should only extend in one direction; however, this value is crucial because it is the highest path sum for the subtree for which root is the highest point.
The global variable ans is updated with the maximum of its current value and the newly calculated sum (ans = max(ans, root.val + left + right)). This step is essential because ans keeps track of the maximum path sum found in the entire tree, including paths that do not extend to the root of the entire tree.
Finally, dfs returns root.val + max(left, right), taking into account the current node's value and the maximum contribution from either the left or right child. This allows the function to relay upward through the recursion the best path sum contribution of the current node to its parent.

The overall maximum path sum is found by setting the initial value of ans to -inf to ensure that any path sum in the tree will be larger (since the tree is non-empty), and then calling dfs(root) which triggers the recursive process. The final value of ans after the recursion completes gives us the result we are seeking – the maximum path sum of any non-empty path in the given binary tree.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small binary tree example:

Consider the following binary tree:

         5
        / \
       4   8
      /   / \
     11  13  4
    /  \      \
   7    2      1

We want to find the maximum path sum in this tree using the solution approach described.

Start with the function dfs at the root node with the value 5.
The dfs function is called recursively on the left child 4 and the function call sequence continues down to 11.
At 11, dfs goes to 7 (left child), which returns 7 because it is a leaf node.
Then dfs goes to the 2 (right child), which returns 2.
At node 11, the function now has left and right values: the dfs result from the left is 7 and the right is 2. Node 11 itself has a value of 11, so the local maximum we can generate at this node (including its value and both children) is 11 + 7 + 2 = 20. However, for the purposes of propagation up the tree, we return 11 + max(7, 2) = 11 + 7 = 18.
The global maximum ans is updated if 20 is greater than the current value of ans.
The recursion unfolds, and a similar process occurs for node 4 on the left and for 8, 13, 4, and 1 on the right side of the tree.
At node 5, the maximum path sums from left and right sides are collected (already calculated by dfs for child nodes).
The overall maximum path that can be formed including node 5 and its children is compared against the global maximum ans. The value returned is 5 + max(left, right) to propagate up the tree.
In each step, whenever a higher path sum is found at a node, the global maximum ans is updated.
The process continues until the topside of the recursion, where the dfs function was initially called with the root of the tree.
The final value of ans after recursion completes represents the maximum path sum from any sequence of nodes in the given binary tree.

For our example, let's assume that the left side (with nodes 5, 4, and 11) produces a path sum of 18, and the right side (with nodes 5, 8, 4, and 1) produces a path sum of 18 as well. The highest path sum that includes the root would be 5 + 18 + 18 = 41. But suppose there's an even higher sum path that doesn't include the root, say 13 + 8 + 4, which equals 25 (node 13 is the root of this path). Hence, the final answer for this example would depend on which sum is larger, and ans would be updated with the maximum sum found.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def maxPathSum(self, root: TreeNode) -> int:
10        # Helper function to perform depth-first search
11        def dfs(node: TreeNode) -> int:
12            # Base case: if the current node is None, return 0
13            if not node:
14                return 0
15
16            # Recursively calculate the maximum path sum on the left subtree
17            # If negative, we take 0 to avoid decreasing the overall path sum
18            left_max = max(0, dfs(node.left))
19          
20            # Similarly, do the same for the right subtree
21            right_max = max(0, dfs(node.right))
22          
23            # Update the overall maximum path sum
24            # This includes the node value and the maximum paths from both subtrees
25            nonlocal max_path_sum
26            max_path_sum = max(max_path_sum, node.val + left_max + right_max)
27          
28            # Return the maximum path sum without splitting
29            # The current node's value plus the greater of its left or right subtree paths
30            return node.val + max(left_max, right_max)
31
32        # Initialize the overall maximum path sum to negative infinity
33        # To account for potentially all negative-valued trees
34        max_path_sum = float('-inf')
35      
36        # Start DFS with the root of the tree
37        dfs(root)
38      
39        # After DFS is done, max_path_sum holds the maximum path sum for the tree
40        return max_path_sum
41

1class Solution {
2    private int maxSum = Integer.MIN_VALUE;  // Initialize maxSum with the smallest possible integer value.
3
4    // Returns the maximum path sum of any path that goes through the nodes of the given binary tree.
5    public int maxPathSum(TreeNode root) {
6        calculateMaxPathFromNode(root);
7        return maxSum;
8    }
9
10    // A helper method that computes the maximum path sum from a given node and updates the overall maxSum.
11    private int calculateMaxPathFromNode(TreeNode node) {
12        if (node == null) {
13            // If the current node is null, we return 0 since null contributes nothing to the path sum.
14            return 0;
15        }
16        // Compute and get the maximum sum of paths from the left child;
17        // if the value is negative, we ignore the left child's contribution by taking 0.
18        int leftMaxSum = Math.max(0, calculateMaxPathFromNode(node.left));
19        // Compute and get the maximum sum of paths from the right child;
20        // if the value is negative, we ignore the right child's contribution by taking 0.
21        int rightMaxSum = Math.max(0, calculateMaxPathFromNode(node.right));
22        // Update maxSum with the greater of the current maxSum or the sum of the current node value plus leftMaxSum and rightMaxSum.
23        // This accounts for the scenario where the path involving the current node and its left and right children yields the max path sum.
24        maxSum = Math.max(maxSum, node.val + leftMaxSum + rightMaxSum);
25        // This call must return the maximum path sum including the currently evaluated node and one of its subtrees
26        // since a path cannot have branches and must be straight through the parents or children nodes.
27        return node.val + Math.max(leftMaxSum, rightMaxSum);
28    }
29}
30
31/**
32 * Definition for a binary tree node.
33 */
34class TreeNode {
35    int val;
36    TreeNode left;
37    TreeNode right;
38
39    TreeNode() {}
40
41    TreeNode(int val) {
42        this.val = val;
43    }
44
45    TreeNode(int val, TreeNode left, TreeNode right) {
46        this.val = val;
47        this.left = left;
48        this.right = right;
49    }
50}
51

1// Definition for a binary tree node.
2struct TreeNode {
3    int val;            // Node's value
4    TreeNode *left;     // Pointer to the left child
5    TreeNode *right;    // Pointer to the right child
6    // Constructors
7    TreeNode() : val(0), left(nullptr), right(nullptr) {}
8    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10};
11
12class Solution {
13public:
14    int maxPathSum(TreeNode* root) {
15        int maxValue = INT_MIN; // Initialize the maximum path sum as the smallest possible integer.
16
17        // Depth-first search function to explore nodes and calculate max path sum.
18        std::function<int(TreeNode*)> depthFirstSearch = [&](TreeNode* node) {
19            if (!node) {
20                return 0; // Base case: If the node is null, return 0 as it adds nothing to the path sum.
21            }
22            // Recursively calculate the max path sum for the left and right children, ignoring negative sums.
23            int leftMax = std::max(0, depthFirstSearch(node->left));
24            int rightMax = std::max(0, depthFirstSearch(node->right));
25
26            // Update the global max path sum by considering the current node value and its maximum left and right path sums.
27            maxValue = std::max(maxValue, leftMax + rightMax + node->val);
28
29            // Return the maximum path sum of either the left or right subtree plus the current node value.
30            return node->val + std::max(leftMax, rightMax);
31        };
32
33        // Start DFS from root.
34        depthFirstSearch(root);
35
36        return maxValue; // Return the global maximum path sum found.
37    }
38};
39

1// Definition for a binary tree node.
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
7        this.val = (val === undefined ? 0 : val);
8        this.left = (left === undefined ? null : left);
9        this.right = (right === undefined ? null : right);
10    }
11}
12
13// Initialize a global variable to hold the maximum path sum
14let maxPathSumValue = -1001;
15
16/**
17 * Helper function to calculate the maximum path sum
18 * @param {TreeNode | null} node - The current node of the binary tree
19 * @return {number} The maximum sum from the current node to any leaf
20 */
21function maxPathSumDfs(node: TreeNode | null): number {
22    // Base case: If the node is null, return 0
23    if (!node) {
24        return 0;
25    }
26  
27    // Calculate maximum sum starting from left child
28    const leftMax = Math.max(0, maxPathSumDfs(node.left));
29  
30    // Calculate maximum sum starting from right child
31    const rightMax = Math.max(0, maxPathSumDfs(node.right));
32  
33    // Update global maxPathSumValue with the maximum sum of the current subtree
34    // which includes the current node and both left and right maximum sums
35    maxPathSumValue = Math.max(maxPathSumValue, leftMax + rightMax + node.val);
36  
37    // Return the maximum sum from current node to any leaf
38    return Math.max(leftMax, rightMax) + node.val;
39}
40
41/**
42 * Function to find the maximum path sum of a binary tree
43 * @param {TreeNode | null} root - The root of the binary tree
44 * @return {number} The maximum path sum in the binary tree
45 */
46function maxPathSum(root: TreeNode | null): number {
47    maxPathSumDfs(root); // Call the helper function starting from the root
48    return maxPathSumValue; // Return the global maximum path sum
49}
50

Time and Space Complexity

// The time complexity of the code is O(n) because the dfs function visits each node in the binary tree exactly once, where n is the number of nodes in the binary tree.

// The space complexity of the code is O(h), where h is the height of the tree. This is due to the recursion stack during the depth-first search (DFS). In the worst case of a skewed tree, the space complexity becomes O(n), where n is the number of nodes, because the height of the tree can be n in the case of a completely unbalanced tree. For a balanced tree, the space complexity would be O(log n), because the height h would be proportional to log n.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]

dp[i] = dp[i - 1] + 1

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

dp[i] = dp[i - 1]

I don’t know