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.

Examples

Example 1:

1
2
3

       1
      / \
     2   3

1
2
3

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:

1
2
3
4
5

     -10
      / \
     9   20
        /  \
       15   7

1
2
3

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.
Similar Problems

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - DFS but Naive

Intuition

The most straightforward way to think about this is to test every possible path. A simpler (but still slow) way to do this is to consider every single node in the tree as the potential “peak” or the highest point of a path. If we calculate the best possible “V”-shaped path (upside down) that is centered at each node, the largest one we find must be the answer.

Approach

  1. Iterate Through All Nodes: We traverse the entire tree, and for each node, we treat it as the “peak” of a potential maximum path.
  2. Calculate Downward Paths: For each peak node, we need to find the longest possible path going downwards from its left child (left_sum) and its right child (right_sum). This requires a separate helper function that does a downward traversal from each child.
  3. Handle Negative Branches: If the longest downward path from a child has a negative sum, it will only decrease our total. Therefore, we should ignore it. We calculate this as max(0, left_sum) and max(0, right_sum).
  4. Calculate Peak Path: The best path centered at the current peak is node.val + max(0, left_sum) + max(0, right_sum).
  5. Track Global Maximum: We keep a global maximum variable and compare it with the peak path sum we just calculated for every node in the tree.
  6. Bottleneck: This approach is inefficient (O(n^2)) because for every node we select as a peak, we start new traversals to find its left_sum and right_sum. This means we re-calculate the downward paths for the same subtrees over and over again.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// Naive O(n^2) Solution
class SolutionNaive {
    int max_sum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        traverse(root);
        return max_sum;
    }

    // 1. Traverse every node, treating each as a potential "peak"
    private void traverse(TreeNode node) {
        if (node == null) {
            return;
        }

        // For the current peak node, find the best downward paths on each side
        int leftDownwardSum = Math.max(0, findMaxDownwardPath(node.left));
        int rightDownwardSum = Math.max(0, findMaxDownwardPath(node.right));

        // Update the global max with the "V" path centered at the current node
        max_sum = Math.max(max_sum, node.val + leftDownwardSum + rightDownwardSum);

        // Continue traversing to check all other nodes as potential peaks
        traverse(node.left);
        traverse(node.right);
    }

    // 2. Helper to find the max path sum starting from a node and going DOWNWARDS
    private int findMaxDownwardPath(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftPath = findMaxDownwardPath(node.left);
        int rightPath = findMaxDownwardPath(node.right);

        // A downward path can only choose one side to continue
        return node.val + Math.max(0, Math.max(leftPath, rightPath));
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# Naive O(n^2) Solution
from typing import Optional

class SolutionNaive:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.max_sum = float('-inf')
        self._traverse(root)
        return self.max_sum

    # 1. Traverse every node, treating each as a potential "peak"
    def _traverse(self, node: Optional[TreeNode]):
        if not node:
            return

        # For the current peak node, find the best downward paths on each side
        left_downward_sum = max(0, self._find_max_downward_path(node.left))
        right_downward_sum = max(0, self._find_max_downward_path(node.right))

        # Update the global max with the "V" path centered at the current node
        self.max_sum = max(self.max_sum, node.val + left_downward_sum + right_downward_sum)

        # Continue traversing to check all other nodes as potential peaks
        self._traverse(node.left)
        self._traverse(node.right)

    # 2. Helper to find the max path sum starting from a node and going DOWNWARDS
    def _find_max_downward_path(self, node: Optional[TreeNode]) -> int:
        if not node:
            return 0

        left_path = self._find_max_downward_path(node.left)
        right_path = self._find_max_downward_path(node.right)

        # A downward path can only choose one side to continue
        return node.val + max(0, left_path, right_path)

Complexity

  • ⏰ Time complexity: O(n^2), as for each of the n nodes in the tree, we potentially traverse all its descendant nodes to find the longest left and right paths. In the worst case of a skewed tree, this results in an O(n) operation for each of the n nodes, leading to a quadratic time complexity.
  • 🧺 Space complexity: O(h). The space is dominated by the recursion stack for the traversal. In the worst case of a completely unbalanced tree, the recursion depth can be n, leading to a linear space complexity.

Method 2 - Optimal Postorder DFS

The bottleneck in the naive approach was re-calculation. We can eliminate this by getting all the information we need in a single pass. The key insight is to use a post-order traversal and design a recursive function that does two jobs at once:

  1. Calculate a potential answer with itself as the peak.
  2. Provide its parent with the best straight path it can contribute.

This avoids recalculating subproblems.

For each node, there are four possible paths for the maximum path sum:

  1. Only the node itself
  2. The maximum path through the left child plus the node
  3. The maximum path through the right child plus the node
  4. The maximum path through the left child, the node, and the right child

The key is to track these four paths and select the highest value at the end.

Approach

We design a recursive dfs(node) function that performs these two jobs:

  1. Base Case: If the node is null, it can’t contribute to any path, so we return 0.

  2. Post-Order Traversal: Recursively call dfs on the left and right children.

    • left_gain = max(0, dfs(node.left))
    • right_gain = max(0, dfs(node.right))
    • We use max(0, ...) here for a critical reason: if a child returns a negative path contribution, we are better off not including that branch at all. This is how the algorithm “cuts” a path and decides where a new one should begin.

  3. Job 1: Update Global Maximum: With the gains from the children calculated, we now check for a new maximum path with the current node as the peak.

    • max_sum = max(max_sum, node.val + left_gain + right_gain)
    • This max_sum is a global (or class-level) variable that tracks the best path found so far anywhere in the tree.

  4. Job 2: Return Value for Parent: The function must return the best possible straight path it can offer its parent. A path cannot split, so it can only include the node and one of its children’s paths.

    • return node.val + max(left_gain, right_gain)
Note

It is important to understand that each subtree’s root must return the maximum path sum that includes at most one child. This is necessary for the call to the parent function. In the code below, this sum is called maxOne and it is what the recursive function returns.

Why don’t we return the sum of node.val + node.left + node.right (lets name it - pathSumWithCurrNodeAsPeak) in the last line? Including pathSumWithCurrNodeAsPeak in the maxPathSum would violate the principle that each node can be traversed only once. Since it is impossible to traverse from node->left->right->node’s parent without revisiting the node itself, we cannot include currTwo in the return value.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int ans;

    public int maxPathSum(TreeNode root) {
        ans = Integer.MIN_VALUE;
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // Get the max path sum from left and right subtrees
        int leftSum = Math.max(0, dfs(node.left));
        int rightSum = Math.max(0, dfs(node.right));

        // Check if the current node is the "peak" of a new max path
        ans = Math.max(ans, node.val + leftSum + rightSum);

        // Return the max path sum for a "straight" path
        return node.val + Math.max(leftSum, rightSum);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// We can also use an array to store value for recursive methods. As, java is not pass by value, we have to use `array` or `AtomicInteger`.

Class Solution {
	public int maxPathSum(TreeNode root) {
		int max[] = new int[1];
		max[0] = Integer.MIN_VALUE;
		dfs(root, max);
		return max[0];
	}
	
	public int dfs(TreeNode root, int[] max) {
		if (root == null) return 0;
	
		int leftMax = dfs(root.left, max);
		int rightMax = dfs(root.right, max);
		
		int maxOne = Math.max(root.val, root.val + Math.max(leftMax, rightMax));
		
		int currTwo = leftMax + root.val + rightMax;
	
		max[0] = Math.max(max[0], Math.max(maxOne, currTwo));
	
		return maxOne;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// We can also use stream api to compare max of 2+ values:
public int dfs(TreeNode root, int[] max) {
	if (root == null) return 0;

	int left = calculateSum(root.left, max);
	int right = calculateSum(root.right, max);

	int maxOne = Stream.of(root.val, root.val + left, root.val + right).max().getInteger();
	
	int currTwo = leftMax + root.val + rightMax;

	max[0] = Stream.of(max[0], maxOne, currTwo).max().getInteger();

	return maxOne;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from typing import Optional

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.ans = float('-inf')

        def dfs(node: Optional[TreeNode]) -> int:
            if not node:
                return 0

            # Get the max path sum from left and right subtrees
            left_sum = max(0, dfs(node.left))
            right_sum = max(0, dfs(node.right))

            # Check if the current node is the "peak" of a new max path
            self.ans = max(self.ans, node.val + left_sum + right_sum)

            # Return the max path sum for a "straight" path
            return node.val + max(left_sum, right_sum)

        dfs(root)
        return self.ans

Dry Run Examples

Example 1

Our goal is to find the maximum path sum. Now consider the following example.

1
2
3

   10
  /  \
null null

In this simple case we know that the max sum would be just the root node itself and the answer would be 10. So fo all leaf nodes the max sum path is the value of the node itself.

Example 2

Now let’s consider the following example.

1
2
3

   20
  /  \
10    30

Here there are multiple possibilities and we need to take care of the following FOUR PATHS that could be our max.

  1. The root iself : 20
  2. The root with the maximum from it’s left subTree : = 10 + 20
1
2
3

    	20
    	/
      10
  1. The root with the maximum from it’s right subTree : = 30 + 20
1
2
3

		20
		  \
	       30
  1. The root with it’s left, right and itself = 60
1
2
3

   	 20
   	 / \
    10  30

In case you are wondering why we did not choose the root.left (10) or root.right(30) alone in the calculation ( like I wondered ), that’s because we would have already computed the result of it as a node in our recursion separately.