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:
[1, 3 * 104].-1000 <= Node.val <= 1000Problem Overview: Given a binary tree, compute the maximum sum of any path. A path can start and end at any node, but it must follow parent-child connections. The path does not need to pass through the root.
Approach 1: Recursive Depth-First Search (O(n) time, O(h) space)
This approach performs a post-order traversal using depth-first search. For every node, compute the maximum contribution it can send to its parent. That contribution is node.val + max(leftGain, rightGain), where negative gains are treated as zero. At each node, also evaluate a candidate path that passes through the node using leftGain + node.val + rightGain and update a global maximum. Each node is processed once, giving O(n) time complexity and O(h) recursion stack space where h is tree height. This approach works well because it separates two ideas: the best downward path contribution and the best full path passing through a node.
Approach 2: Dynamic Programming with Tree Traversal (O(n) time, O(h) space)
This method frames the same traversal as a dynamic programming problem on a binary tree. Each node stores the best downward path sum that can extend to its parent. During traversal, compute two values: the best downward extension and the best path passing through the current node using both children. The DP transition is straightforward: ignore negative child paths, update the global maximum with the combined path, and return the best single-branch extension upward. The algorithm still visits each node exactly once, so time complexity remains O(n), with recursion stack space O(h).
Recommended for interviews: The recursive DFS solution is what most interviewers expect. It clearly demonstrates understanding of tree traversal and how to maintain global state during recursion. Explaining why negative child sums are ignored and how the "split path" is evaluated at each node shows strong problem-solving depth.
This approach uses a recursive depth-first search (DFS) to explore every path in the binary tree. We calculate the maximum path sum that a node can contribute to its parent, which is the largest possible sum of the path from this node to any leaf node passing through this node. We keep updating the global maximum path sum during the recursion.
We define a nested function dfs that takes a node as an input and returns the maximum sum of the path that includes the node as an endpoint. The function recursively calculates the maximum path sum of the left and right subtrees. It then calculates the maximum path sum that includes the current node. We maintain a global variable dfs.max_sum to keep track of the maximum path sum encountered so far. Finally, the function returns the maximum path sum starting at the current node. We initialize the maximum path sum to negative infinity to ensure any path replaces it.
C++
JavaScript
Time Complexity: O(n), where n is the number of nodes in the binary tree. We traverse each node exactly once.
Space Complexity: O(h), where h is the height of the tree. This space is used by the call stack for recursion.
In this approach, we utilize dynamic programming principles alongside tree traversal to compute the maximum path sum. This method is more about reformulating the tree's recursive structure into a form that allows storing intermediate results to optimize operations across the different subtrees. This method is especially useful for understanding different formulations but often overlaps logically with recursive DFS.
In this solution, we employ a recursive method calculateMaxSum that computes sub-results by leveraging already seen sub-tree sub-results. By traversing each node once, we update a global max value maxSum with results derived from each node acting as a center of a new path. This method hence avoids recomputation by relying on previously calculated results, drawing dynamic programming parallels.
C#
Time Complexity: O(n), covering a single pass over all nodes.
Space Complexity: O(h), necessitated by call stack usage designated by the tree height h.
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search Approach | Time Complexity: O(n), where n is the number of nodes in the binary tree. We traverse each node exactly once. |
| Dynamic Programming with Tree Traversal Approach | Time Complexity: O(n), covering a single pass over all nodes. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search | O(n) | O(h) | Standard solution for interview settings; simple recursion with global max tracking |
| Dynamic Programming with Tree Traversal | O(n) | O(h) | When framing the problem as tree DP and explaining state transitions |
L17. Maximum Path Sum in Binary Tree | C++ | Java • take U forward • 420,687 views views
Watch 9 more video solutions →Practice Binary Tree Maximum Path Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor