Log inSign up
hardleetcodeNot Started

Binary Tree Maximum Path Sum

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

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 · Example 1: Positive Tree:

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

Example 2 · Example 2: Negative Root with Large Positive Subtree:

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

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Distinguish between a complete path through an apex and an extendable branch sum.
  • Handle negative node values gracefully using Math.max(0, ...).
  • Implement bottom-up dynamic programming on trees in a single pass.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Maximum path sum in tree.
  • Path does NOT need to pass through root.
  • Nodes can have negative values.

Algorithmic Decision Tree:

  • At each node: leftGain = max(0, maxPathDown(node.left)), rightGain = max(0, maxPathDown(node.right)).
  • Update globalMax = max(globalMax, node.val + leftGain + rightGain).
  • Return node.val + max(leftGain, rightGain) to parent.

Connected Patterns:

Diameter of Binary TreeHouse Robber IIIPath Sum III

1. Evaluate Max Path Through Every Node (Recomputation)

Intuition

For each node u in the tree, calculate maxPathDown(u->left) and maxPathDown(u->right). Sum them with u->val to find the max path turning at u. Repeat for all nodes.

When to apply: Basic baseline intuition.

Algorithm

  1. Step 1: Helper maxDown(node) computes max path sum going strictly downwards from node.
  2. Step 2: For current node: pathThroughNode = node.val + max(0, maxDown(left)) + max(0, maxDown(right)).
  3. Step 3: Recurse on left child and right child to find max path not passing through node.
  4. Step 4: Return overall max.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int maxDown(TreeNode* node) {
10 if (!node) return 0;
11 int left = max(0, maxDown(node->left));
12 int right = max(0, maxDown(node->right));
13 return node->val + max(left, right);
14 }
15 int maxPathSum(TreeNode* root) {
16 if (!root) return INT_MIN;
17 int leftDown = max(0, maxDown(root->left));
18 int rightDown = max(0, maxDown(root->right));
19 int currentMax = root->val + leftDown + rightDown;
20 int leftSub = maxPathSum(root->left);
21 int rightSub = maxPathSum(root->right);
22 return max({currentMax, leftSub, rightSub});
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n^2) — For each of the n nodes, maxDown traverses the subtree in O(n) time.
  • Space complexity: O(h) — Call stack up to O(h).

2. Postorder DFS with Global Array Variable

Intuition

Perform postorder DFS. Bottom-up returns max downward gain for each subtree. At each step, update global max path sum array.

When to apply: Clean single-pass implementation using pass-by-reference.

Algorithm

  1. Step 1: Initialize globalMax array = [-Infinity].
  2. Step 2: Helper dfs(node): if null return 0.
  3. Step 3: leftGain = max(0, dfs(node.left)), rightGain = max(0, dfs(node.right)).
  4. Step 4: Update globalMax[0] = max(globalMax[0], node.val + leftGain + rightGain).
  5. Step 5: Return node.val + max(leftGain, rightGain).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int dfs(TreeNode* node, int& maxVal) {
10 if (!node) return 0;
11 int left = max(0, dfs(node->left, maxVal));
12 int right = max(0, dfs(node->right, maxVal));
13 maxVal = max(maxVal, node->val + left + right);
14 return node->val + max(left, right);
15 }
16 int maxPathSum(TreeNode* root) {
17 int maxVal = INT_MIN;
18 dfs(root, maxVal);
19 return maxVal;
20 }
21};
22
23int main() {
24 // Sample driver execution
25 cout << "Execution completed successfully." << endl;
26 return 0;
27}
28

Time & Space Complexity

  • Time complexity: O(n) — Every node visited exactly once.
  • Space complexity: O(h) — Recursion stack depth is proportional to tree height h.

3. Optimal Bottom-Up Postorder DP (Single Pass)

Intuition

Each node calculates its maximum downward gain to offer to its parent: node.val + max(0, max(leftGain, rightGain)). Simultaneously, it tests whether the path with this node as the apex (node.val + max(0, leftGain) + max(0, rightGain)) exceeds the global max.

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: Set maxResult = -Infinity.
  2. Step 2: Define helper postorder(node): returns maximum path from node down to any descendant.
  3. Step 3: Base case: if node is null return 0.
  4. Step 4: Compute left = Math.max(0, postorder(node.left)) and right = Math.max(0, postorder(node.right)).
  5. Step 5: maxResult = Math.max(maxResult, node.val + left + right).
  6. Step 6: Return node.val + Math.max(left, right).

Bottom-Up DFS Trace for [-10, 9, 20, null, null, 15, 7]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Inspect leaf 9 (gain 9) and leaf 20 (gain 20)
Visual state
Values and pointers at this exact step
tree
Root
-10
L
9
R (Max Apex)
20

Node order shown; add connections to display explicit tree edges.

maxSum: 20
Check / comparison
Apex at -10: -10 + 9 + 20 = 19. Node 20 alone: 20.
Decision / next transition
Node 20 alone gives higher sum (20 > 19).
Why this step matters

Step 1: Inspect leaf 9 (gain 9) and leaf 20 (gain 20). At root -10, left gain is 9, right gain is 20.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 int maxAns;
9 int gain(TreeNode* root) {
10 if (!root) return 0;
11 int l = max(0, gain(root->left));
12 int r = max(0, gain(root->right));
13 maxAns = max(maxAns, root->val + l + r);
14 return root->val + max(l, r);
15 }
16public:
17 int maxPathSum(TreeNode* root) {
18 maxAns = INT_MIN;
19 gain(root);
20 return maxAns;
21 }
22};
23
24int main() {
25 // Sample driver execution
26 cout << "Execution completed successfully." << endl;
27 return 0;
28}
29

Time & Space Complexity

  • Time complexity: O(n) — Processes each node exactly once in bottom-up order.
  • Space complexity: O(h) — Recursion stack takes O(h) space, which is O(log n) for balanced trees.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force Separate maxDownO(n^2)O(h)Recomputes max downward path for each node from scratch.Repeated subtree scans.
2.Postorder DFS with Array RefO(n)O(h)Single pass computing downward gain and updating global array.None.
3.Optimal Bottom-Up Postorder DPOptimalO(n)O(h)Single bottom-up pass returning single-branch gain and updating global apex maximum.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • All negative values: (e.g. [-3]) -> must return -3, NOT 0 (path must be non-empty).
  • Single node: returns root.val.
  • Skewed tree with mixed positives and negatives: correctly cuts off negative branches.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Initialize globalMax to INT_MIN (or -Infinity) rather than 0, because all tree nodes might be negative.
  2. Explain the distinction between what is computed for the global answer (both branches) vs what is returned up the stack (at most one branch).
  3. Trace with a small tree containing negative values to demonstrate clamping.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the helper function return node.val + max(left, right) rather than node.val + left + right?

Back to DSA Sheet