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: You are given a binary tree where each node contains an integer (positive or negative). A path can start and end at any node, but it must follow parent-child connections. The task is to compute the maximum possible sum of values along any such path.
Approach 1: Recursive Depth-First Search (O(n) time, O(h) space)
This approach performs a postorder traversal using depth-first search. For every node, compute the maximum gain it can contribute to a path that extends upward to its parent. The key insight: a path passing through a node may include both left and right children, but a parent can only continue one side. During recursion, calculate left_gain = max(dfs(left), 0) and right_gain = max(dfs(right), 0). The candidate maximum path through the node becomes node.val + left_gain + right_gain, which updates a global maximum. The recursive function returns node.val + max(left_gain, right_gain) so the parent continues the best single branch. Every node is visited once, giving O(n) time. The recursion stack uses O(h) space where h is tree height.
Approach 2: Dynamic Programming with Tree Traversal (O(n) time, O(h) space)
This approach frames the same idea explicitly as dynamic programming on trees. Each node stores the best downward path sum starting from that node. While traversing the tree (typically postorder), compute two values: the best downward path returned to the parent and the best path passing through the node that may include both children. The recurrence relation is similar: downward = node.val + max(0, left, right). Meanwhile, update a global maximum with node.val + max(0,left) + max(0,right). The DP perspective emphasizes that each node's result depends only on its children’s computed values. Since each node contributes constant work and the traversal touches every node once, the runtime remains O(n) with O(h) auxiliary stack space.
Recommended for interviews: Interviewers typically expect the recursive DFS solution. It shows that you recognize a tree path can branch through a node but only one branch continues upward. Explaining the difference between the "global path" and the "extendable path" demonstrates strong understanding of tree recursion and dynamic programming on trees.
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.
Python
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.
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.
When thinking about the classic routine of recursion problems in binary trees, we consider:
For this problem, we design a function dfs(root), which returns the maximum path sum of the binary tree with root as the root node.
The execution logic of the function dfs(root) is as follows:
If root does not exist, then dfs(root) returns 0;
Otherwise, we recursively calculate the maximum path sum of the left and right subtrees of root, denoted as left and right. If left is less than 0, then we set it to 0, similarly, if right is less than 0, then we set it to 0.
Then, we update the answer with root.val + left + right. Finally, the function returns root.val + max(left, right).
In the main function, we call dfs(root) to get the maximum path sum of each node, and the maximum value among them is the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| 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. |
| Recursion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search | O(n) | O(h) | Standard interview solution. Clean recursion with global maximum tracking. |
| Dynamic Programming with Tree Traversal | O(n) | O(h) | When explaining the problem as DP on trees or implementing structured tree DP. |
Binary Tree Maximum Path Sum - DFS - Leetcode 124 - Python • NeetCode • 235,579 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