Binary Tree Maximum Path Sum solution and explanation
Google
9 more videos on this problem
Binary Tree Maximum Path Sum - DFS - Leetcode 124 - PythonNeetCode · 15:19 · 247K views
Binary tree maximum path sum | Leetcode #124Techdose · 15:23 · 57K views
LeetCode 124. Binary Tree Maximum Path Sum (Algorithm Explained)Nick White · 16:16 · 39K views
Binary Tree Maximum Path Sum - (Google, Meta, Amazon, Flipkart) : Explanation ➕ Live CodingcodestorywithMIK · 26:35 · 35K views
Binary Tree Maximum Path Sum (Animated Walkthrough) (LeetCode)AlgosWithMichael · 11:43 · 27K views
[Java] Leetcode 124. Binary Tree Maximum Path Sum [Binary Tree #16]Eric Programming · 10:21 · 3K views
BINARY TREE MAX PATH SUM | PYTHON | LEETCODE 124Cracking FAANG · 20:16 · 3K views
Binary Tree Maximum Path Sum - LeetCode 124 - Python #leetcode #binarytree #blind75 #recursionDeepti Talesra · 12:47 · 2K views
LeetCode 124. Binary Tree Maximum Path Sum [Coding Interview Solution Explained]Shiran Afergan · 18:28 · 1K views
Binary Tree Maximum Path Sum - LeetCode 124 - JavaScriptAlgoJS · 7:38 · 1K views
The problem
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 * 104]. -1000 <= Node.val <= 1000
Approach overview
Problem 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.
Approach 1: Recursive Depth-First Search Approach
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxPathSum(root):
def dfs(node):
if not node:
return 0
left_max = max(dfs(node.left), 0)
right_max = max(dfs(node.right), 0)
current_path_sum = node.val + left_max + right_max
dfs.max_sum = max(dfs.max_sum, current_path_sum)
return node.val + max(left_max, right_max)
dfs.max_sum = float('-inf')
dfs(root)
return dfs.max_sum#include <limits.h>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int maxPathSum(TreeNode* root) {
int max_sum = INT_MIN;
maxGain(root, max_sum);
return max_sum;
}
int maxGain(TreeNode* node, int &max_sum) {
if (!node) return 0;
int left_gain = std::max(maxGain(node->left, max_sum), 0);
int right_gain = std::max(maxGain(node->right, max_sum), 0);
int price_newpath = node->val + left_gain + right_gain;
max_sum = std::max(max_sum, price_newpath);
return node->val + std::max(left_gain, right_gain);
}
};function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
function maxPathSum(root) {
let maxSum = -Infinity;
function dfs(node) {
if (node === null) return 0;
let leftMax = Math.max(dfs(node.left), 0);
let rightMax = Math.max(dfs(node.right), 0);
let currentPathSum = node.val + leftMax + rightMax;
maxSum = Math.max(maxSum, currentPathSum);
return node.val + Math.max(leftMax, rightMax);
}
dfs(root);
return maxSum;
}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.
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.
Approach 2: Dynamic Programming with Tree Traversal Approach
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.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
calculateMaxSum(root);
return maxSum;
}
private int calculateMaxSum(TreeNode node) {
if (node == null) return 0;
int leftGain = Math.max(calculateMaxSum(node.left), 0);
int rightGain = Math.max(calculateMaxSum(node.right), 0);
int priceNewPath = node.val + leftGain + rightGain;
maxSum = Math.max(maxSum, priceNewPath);
return node.val + Math.max(leftGain, rightGain);
}
}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 maxSum = int.MinValue;
public int MaxPathSum(TreeNode root) {
CalculateMaxSum(root);
return maxSum;
}
private int CalculateMaxSum(TreeNode node) {
if (node == null) return 0;
int leftGain = Math.Max(CalculateMaxSum(node.left), 0);
int rightGain = Math.Max(CalculateMaxSum(node.right), 0);
int currentPath = node.val + leftGain + rightGain;
maxSum = Math.Max(maxSum, currentPath);
return node.val + Math.Max(leftGain, rightGain);
}
}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.
Approach 3: Recursion
When thinking about the classic routine of recursion problems in binary trees, we consider:
- Termination condition (when to terminate recursion)
- Recursively process the left and right subtrees
- Merge the calculation results of the left and right subtrees
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.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function maxPathSum(root: TreeNode | null): number {
let ans = -1001;
const dfs = (root: TreeNode | null): number => {
if (!root) {
return 0;
}
const left = Math.max(0, dfs(root.left));
const right = Math.max(0, dfs(root.right));
ans = Math.max(ans, left + right + root.val);
return Math.max(left, right) + root.val;
};
dfs(root);
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxPathSum(root *TreeNode) int {
ans := -1001
var dfs func(*TreeNode) int
dfs = func(root *TreeNode) int {
if root == nil {
return 0
}
left := max(0, dfs(root.Left))
right := max(0, dfs(root.Right))
ans = max(ans, left+right+root.Val)
return max(left, right) + root.Val
}
dfs(root)
return ans
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, res: &mut i32) -> i32 {
if root.is_none() {
return 0;
}
let node = root.as_ref().unwrap().borrow();
let left = (0).max(Self::dfs(&node.left, res));
let right = (0).max(Self::dfs(&node.right, res));
*res = (node.val + left + right).max(*res);
node.val + left.max(right)
}
pub fn max_path_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
let mut res = -1000;
Self::dfs(&root, &mut res);
res
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Binary Tree Maximum Path Sum easy or hard?
Binary Tree Maximum Path Sum is classified as a Hard problem because it requires understanding two different path concepts: the extendable path returned to the parent and the complete path passing through a node. Handling negative values and combining subtree results correctly makes it challenging.
Binary Tree Maximum Path Sum Python/Java solution
Python and Java implementations both use recursive DFS. The helper function returns the maximum gain from the current node while updating a global maximum path sum. Both implementations run in O(n) time and require O(h) stack space.
How to solve Binary Tree Maximum Path Sum in O(n)?
Perform a postorder DFS traversal and compute the maximum gain from each node. For each node, calculate left_gain and right_gain, ignoring negative contributions by clamping them to zero. Update a global maximum with node.val + left_gain + right_gain, and return node.val + max(left_gain, right_gain) to the parent.
What is the best approach for Binary Tree Maximum Path Sum?
The optimal approach uses depth-first search with dynamic programming on the tree. During a postorder traversal, compute the maximum gain from each child and update a global maximum path sum at every node. This solution processes each node once, giving O(n) time complexity and O(h) recursion stack space.
Is Binary Tree Maximum Path Sum asked at Google/Amazon/Meta?
Binary Tree Maximum Path Sum is a well-known hard tree problem frequently reported in interviews at companies like Google, Amazon, Meta, and Microsoft. It tests depth-first search, recursion, and the ability to reason about paths in trees with negative values.
What data structure is used in Binary Tree Maximum Path Sum?
The problem operates on a binary tree data structure. The solution typically uses recursion with depth-first search and maintains a global variable to track the maximum path sum while traversing the tree.
What is the time complexity of Binary Tree Maximum Path Sum?
The time complexity is O(n) where n is the number of nodes in the binary tree. Each node is visited exactly once during the DFS traversal. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.