Find the Maximum Path Sum in a Binary Tree

Given the root of a binary tree, return the maximum path sum among all non-empty paths in the tree.

A path is a sequence of connected nodes where no node appears more than once. The path may start and end at any nodes and does not need to pass through the root.

Since node values may be negative, the maximum path sum can also be negative.

Example 1

Input: root = [1, 2, 3]

Output: 6

Explanation: The best path is 2 -> 1 -> 3. The sum is 2 + 1 + 3 = 6.

Example 2

Input: root = [-10, 9, 20, null, null, 15, 7]

Output: 42

Explanation: The best path is 15 -> 20 -> 7. Its sum is 15 + 20 + 7 = 42. The root -10 is not included because it reduces the sum.

Example 3

Input: root = [-3]

Output: -3

Explanation: The path must be non-empty. Since there is only one node, the best path contains that node itself, so the answer is -3.

Practice it by yourself before moving onto the solutionTry now

Brute Force Approach

Any node can act as the highest point of a path. From that node, the path may take the best downward contribution from its left subtree, the best downward contribution from its right subtree, or neither if a contribution is negative.

So, for every node, calculate:

node value + useful left gain + useful right gain

The answer cannot be checked only at the root because the best path may lie completely inside a subtree.

The drawback is that the best downward gain of the same subtree is recalculated for many different nodes, causing repeated work.

Algorithm

A helper findMaxDownwardPath is used to calculate the best path sum that starts at a node and continues downward through at most one child.
For a null node, 0 is returned because an empty branch contributes nothing to a downward path.
For every non-null node, the best downward gains from the left and right children are calculated, while negative gains are replaced with 0 so that they do not reduce the path sum.
The value node value + max(leftGain, rightGain) is returned because an extendable path can continue through only one child.
For every node, the useful left and right contributions are calculated and combined with the current node as node value + leftContribution + rightContribution to represent the complete path passing through that node.
The left and right subtrees are also checked recursively, and the maximum among the current path, the best left-subtree path, and the best right-subtree path is returned.

Dry Run

Maximum Path Sum Brute Force Dry Run.png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int x) {
      val = x;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17private:
  // Returns the best path starting
  // here and moving through one child.
  int findMaxDownwardPath(TreeNode* root) {
      if (root == nullptr) {
          return 0;
      }
24
      // Negative branches are ignored
      // because they reduce the path sum.
      int leftGain = max(
          0,
          findMaxDownwardPath(root->left)
      );
31
      // Negative branches are ignored
      // because they reduce the path sum.
      int rightGain = max(
          0,
          findMaxDownwardPath(root->right)
      );
38
      // Only one branch can continue
      // as a downward path.
      return root->val + max(
          leftGain,
          rightGain
      );
  }
46
47public:
  // Finds the best path by considering
  // every node as a turning point.
  int maxPathSum(TreeNode* root) {
      if (root == nullptr) {
          return INT_MIN;
      }
54
      // Negative contributions are skipped
      // while forming the current path.
      int leftContribution = max(
          0,
          findMaxDownwardPath(root->left)
      );
61
      int rightContribution = max(
          0,
          findMaxDownwardPath(root->right)
      );
66
      // Both branches may participate when
      // this node is the path's turning point.
      int currentPath =
          root->val
          + leftContribution
          + rightContribution;
73
      // The best path may lie completely
      // inside either subtree.
      int leftBest = root->left
          ? maxPathSum(root->left)
          : INT_MIN;
79
      int rightBest = root->right
          ? maxPathSum(root->right)
          : INT_MIN;
83
      return max({
          currentPath,
          leftBest,
          rightBest
      });
  }
90};
91
92int main() {
  TreeNode* root = new TreeNode(-10);
  root->left = new TreeNode(9);
  root->right = new TreeNode(20);
  root->right->left = new TreeNode(15);
  root->right->right = new TreeNode(7);
98
  Solution solution;
100
  cout << solution.maxPathSum(root) << endl;
102
  return 0;
104}

Complexity Analysis

Time Complexity: O(N²) in the worst case, where N is the number of nodes in the binary tree. Downward path gains may be recalculated for many different ancestors, causing repeated traversal. In a skewed tree, this repeated work becomes quadratic.

Space Complexity: O(H), where H is the height of the binary tree, due to the recursion stack. This can become O(N) for a skewed tree.

Optimal Approach

The Brute Force Approach already gives the correct path formula. Its only problem is recalculating subtree gains.

Post-order DFS removes that repetition. Each node first receives the best extendable gain from its left and right children.

At the current node, both gains may be used to form a complete candidate path:

node value + leftGain + rightGain

But only one side can be returned to the parent, because a path passed upward must remain a single chain rather than split into two branches.

Negative gains are ignored because including them would only decrease the path sum.

Algorithm

A variable maxSum is initialized with negative infinity or the minimum integer value so that trees containing only negative values are handled correctly.
A recursive helper findMaxGain is used to return the best path sum starting at the current node and extending downward through at most one child.
For a null node, 0 is returned because no contribution is provided by an empty branch.
The left and right gains are calculated recursively, and every negative gain is replaced with 0 because including such a branch would only decrease the path sum.
The complete candidate path through the current node is formed as node value + leftGain + rightGain, and maxSum is updated whenever this candidate is larger.
The value node value + max(leftGain, rightGain) is returned to the parent because only one branch can remain part of a valid upward path.
After the complete post-order traversal has been performed, maxSum is returned as the maximum path sum.

Dry Run

Maximum Path Sum Optimal Approach Dry Run.png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int x) {
      val = x;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17private:
  // Returns the best extendable path
  // starting from the current node.
  int findMaxGain(
      TreeNode* root,
      int& maxSum
  ) {
      if (root == nullptr) {
          return 0;
      }
27
      // Negative left contributions are clamped
      // to 0 to avoid reducing the path sum.
      int leftGain = max(
          0,
          findMaxGain(root->left, maxSum)
      );
34
      // Negative right contributions are clamped
      // to 0 to avoid reducing the path sum.
      int rightGain = max(
          0,
          findMaxGain(root->right, maxSum)
      );
41
      // Both branches may form a complete
      // path through the current node.
      int currentPath =
          root->val
          + leftGain
          + rightGain;
48
      maxSum = max(
          maxSum,
          currentPath
      );
53
      // Only one branch can continue upward
      // without creating a branching path.
      return root->val + max(
          leftGain,
          rightGain
      );
  }
61
62public:
  // Returns the maximum path sum
  // among all non-empty paths.
  int maxPathSum(TreeNode* root) {
      int maxSum = INT_MIN;
67
      findMaxGain(root, maxSum);
69
      return maxSum;
  }
72};
73
74int main() {
  TreeNode* root = new TreeNode(-10);
  root->left = new TreeNode(9);
  root->right = new TreeNode(20);
  root->right->left = new TreeNode(15);
  root->right->right = new TreeNode(7);
80
  Solution solution;
82
  cout << solution.maxPathSum(root) << endl;
84
  return 0;
86}

Note: For a very deep skewed tree, recursive implementations may hit recursion depth limits in Python or stack limits in some environments. The same logic can be written iteratively if the input depth is extremely large.

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes in the binary tree. Every node is processed exactly once, and its best extendable gain is calculated during the same traversal.

Space Complexity: O(H), where H is the height of the binary tree, due to the recursion stack. This becomes O(N) for a skewed tree and O(log N) for a balanced tree.

FAQs

Q1. Why are negative child gains ignored?

A negative contribution can only reduce the current path sum. Since a path may start and end anywhere, there is no requirement to include that branch.

Q2. Why must maxSum start with a very small value instead of 0?

All node values may be negative. Starting with 0 would incorrectly allow an empty path to become the answer. Initializing with negative infinity ensures at least one real node is selected.

Q3. Why can both child gains update maxSum, while only one is returned to the parent?

A complete path may turn at the current node and use both children. However, once that path continues to the parent, it must remain a single chain, so only one child branch can continue upward.

Q4. How is this different from Diameter of Binary Tree?

Both problems use a similar post-order structure. Diameter maximizes the number of edges, while Maximum Path Sum maximizes node values and therefore must also discard negative contributions.

Q5. What is a common implementation mistake?

Returning:

node value + leftGain + rightGain

to the parent. That would create a branching path. The two-sided value is used only to update the global answer; the returned gain must use only one child.

Find the Maximum Path Sum in a Binary Tree

Example 1

Example 2

Example 3

Brute Force Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Optimal Approach

Algorithm

Dry Run

Solution

Complexity Analysis

FAQs

Read Similar Blogs

Vertical Order Traversal of a Binary Tree

Invert Binary Tree

Minimum Time to Burn a Binary Tree from a Given Node