Binary Tree Maximum Path Sum

Hard

#0124Time: O(N^2)Space: O(N)22 companies

Patterns

Dynamic Programming

Algorithms

Depth-First Search

Data structures

Tree Binary Tree

Companies

DoorDash Flipkart Intuit Nutanix

Prompt

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints:

The number of nodes in the tree is in the range [1, 3 * 10⁴].
-1000 <= Node.val <= 1000

Approaches

2 approaches with complexity analysis and trade-offs.

This approach considers every node in the tree as the potential "pivot" or the highest point of the maximum path. For each node chosen as the pivot, we calculate the maximum path sum that can be formed by extending downwards into its left and right subtrees. The overall maximum sum is the maximum of these values calculated for every possible pivot node.

Algorithm

Define a helper function maxPathDown(node):
- If node is null, return 0.
- Recursively find the max path down from the left child: left = max(0, maxPathDown(node.left)).
- Recursively find the max path down from the right child: right = max(0, maxPathDown(node.right)).
- Return node.val + max(left, right).
In the main function maxPathSum(root):
- Initialize max_sum = Integer.MIN_VALUE.
- Perform a traversal (e.g., pre-order) of the tree. For each node visited:
  - Calculate the max path sum going down the left subtree: left_sum = max(0, maxPathDown(node.left)).
  - Calculate the max path sum going down the right subtree: right_sum = max(0, maxPathDown(node.right)).
  - Calculate the path sum with the current node as the pivot: current_max = node.val + left_sum + right_sum.
  - Update the global maximum: max_sum = max(max_sum, current_max).
- Return max_sum.

Walkthrough

The core idea is to iterate through all nodes of the tree. For each node u, we treat it as the root of a path. The path can extend from u's left child downwards and from u's right child downwards.

We need a helper function, let's call it maxPathDown(node), which calculates the maximum sum of a path starting at node and going strictly downwards. The maxPathDown(node) function is recursive: node.val + max(0, maxPathDown(node.left), maxPathDown(node.right)). We take max with 0 to handle cases where the downward path has a negative sum; in such cases, we'd rather not extend the path.

The main algorithm iterates through each node, and for each node, it calls maxPathDown on its children to find the path sum where the current node is the highest point. This approach is inefficient because the maxPathDown function is called repeatedly for the same subtrees. For example, when processing a node u, we compute maxPathDown for its entire left subtree. Later, when we process u's left child as the pivot, we re-do much of the same computation.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    private int overallMaxSum;18 19    public int maxPathSum(TreeNode root) {20        overallMaxSum = Integer.MIN_VALUE;21        traverse(root);22        return overallMaxSum;23    }24 25    // Traverse each node and treat it as the pivot26    private void traverse(TreeNode node) {27        if (node == null) {28            return;29        }30 31        // Calculate the max path sum with the current node as the pivot32        int leftPath = maxPathDown(node.left);33        int rightPath = maxPathDown(node.right);34 35        int leftSum = Math.max(0, leftPath);36        int rightSum = Math.max(0, rightPath);37 38        overallMaxSum = Math.max(overallMaxSum, node.val + leftSum + rightSum);39 40        // Continue to the next nodes41        traverse(node.left);42        traverse(node.right);43    }44 45    // Helper to compute max path sum starting at a node and going down46    private int maxPathDown(TreeNode node) {47        if (node == null) {48            return 0;49        }50        int left = Math.max(0, maxPathDown(node.left));51        int right = Math.max(0, maxPathDown(node.right));52        return node.val + Math.max(left, right);53    }54}

Complexity

Time

O(N^2)

Space

O(N)

Trade-offs

Pros

Conceptually simpler to understand as it separates the problem into two distinct parts: iterating through pivots and calculating downward path sums.

Cons

Highly inefficient due to a large number of redundant calculations.
The maxPathDown function is called for the same nodes multiple times, leading to a poor time complexity.

This is the most efficient approach. It solves the problem in a single pass using a recursive Depth-First Search (DFS). The key insight is to realize that for any node, the information needed by its parent is the maximum path sum starting from the current node and going downwards (in a straight line). At the same time, we can calculate the maximum path sum that has the current node as its highest point (the "pivot").

Algorithm

Initialize a variable max_sum to Integer.MIN_VALUE. This will store the final result.
Define a recursive function maxGain(node):
- Base Case: If node is null, return 0.
- Recursively call maxGain for the left and right children: left_gain = max(0, maxGain(node.left)) and right_gain = max(0, maxGain(node.right)). We use max(0, ...) to discard paths with negative sums.
- Calculate the maximum path sum with the current node as the highest point: current_max_path = node.val + left_gain + right_gain.
- Update the global max_sum: max_sum = max(max_sum, current_max_path).
- Return the maximum gain that can be extended upwards to the parent of node: node.val + max(left_gain, right_gain).
In the main function, call maxGain(root).
Return max_sum.

Walkthrough

We design a recursive helper function, say maxGain(node), that performs a post-order traversal. This function does two things:

Return Value: It returns the maximum path sum starting from node and extending downwards to one of its subtrees (left or right). This value is what the parent of node can use to extend its own path. The value is node.val + max(left_gain, right_gain).
Global Update: It calculates the maximum path sum with node as the "pivot" (i.e., the path can go down both left and right subtrees). This value is node.val + left_gain + right_gain. This path cannot be extended further up, so we don't return it. Instead, we use it to update a global variable that tracks the overall maximum path sum found so far.

The left_gain and right_gain are the results of the recursive calls on the left and right children, respectively. We take max(0, recursive_call_result) because if a subtree's maximum gain is negative, we are better off not including it in our path. The main function initializes a global maximum variable, calls the recursive helper on the root, and then returns the global maximum.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    int maxSum;18 19    public int maxPathSum(TreeNode root) {20        maxSum = Integer.MIN_VALUE;21        maxGain(root);22        return maxSum;23    }24 25    private int maxGain(TreeNode node) {26        if (node == null) {27            return 0;28        }29 30        // Recursively get the maximum path sum from left and right subtrees31        // Discard negative path sums by taking max with 032        int leftGain = Math.max(0, maxGain(node.left));33        int rightGain = Math.max(0, maxGain(node.right));34 35        // Calculate the maximum path sum with the current node as the "pivot"36        // This is a potential candidate for the overall maximum path sum37        int currentPathSum = node.val + leftGain + rightGain;38        39        // Update the global maximum sum40        maxSum = Math.max(maxSum, currentPathSum);41 42        // Return the maximum gain for a path that can be extended by the parent node.43        // This path must go "straight" down from the parent.44        return node.val + Math.max(leftGain, rightGain);45    }46}

Complexity

Time

O(N)

Space

O(H)

Trade-offs

Pros

Highly efficient, solving the problem in a single pass with O(N) time complexity.
Elegant and concise recursive solution.

Cons

The logic can be slightly tricky to grasp initially, as the recursive function serves two purposes: returning a value for its caller and updating a global state.

Solutions

Solution

1/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { private int ans = - 1001 ; public int MaxPathSum ( TreeNode root ) { dfs ( root ); return ans ; } private int dfs ( TreeNode root ) { if ( root == null ) { return 0 ; } int left = Math . Max ( 0 , dfs ( root . left )); int right = Math . Max ( 0 , dfs ( root . right )); ans = Math . Max ( ans , left + right + root . val ); return root . val + Math . Max ( left , right ); } }

1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int ans = - 1001 ; public int maxPathSum ( TreeNode root ) { dfs ( root ); return ans ; } private int dfs ( TreeNode root ) { if ( root == null ) { return 0 ; } int left = Math . max ( 0 , dfs ( root . left )); int right = Math . max ( 0 , dfs ( root . right )); ans = Math . max ( ans , root . val + left + right ); return root . val + Math . max ( left , right ); } }

1/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number} */ var maxPathSum =2  function (root) {3    let ans = -1001;4    const dfs = (root) => {5      if (!root) {6        return 0;7      }8      const left = Math.max(0, dfs(root.left));9      const right = Math.max(0, dfs(root.right));10      ans = Math.max(ans, left + right + root.val);11      return Math.max(left, right) + root.val;12    };13    dfs(root);14    return ans;15  };

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxPathSum ( TreeNode * root ) { int ans = - 1001 ; function < int ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) { if ( ! root ) { return 0 ; } int left = max ( 0 , dfs ( root -> left )); int right = max ( 0 , dfs ( root -> right )); ans = max ( ans , left + right + root -> val ); return root -> val + max ( left , right ); }; dfs ( root ); return ans ; } };

1# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def maxPathSum ( self , root : Optional [ TreeNode ]) -> int : def dfs ( root : Optional [ TreeNode ]) -> int : if root is None : return 0 left = max ( 0 , dfs ( root . left )) right = max ( 0 , dfs ( root . right )) nonlocal ans ans = max ( ans , root . val + left + right ) return root . val + max ( left , right ) ans = - inf dfs ( root ) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem