Binary Tree Maximum Path Sum

Hardtreedepth-first-searchrecursiondynamic-programming
Category: Trees
Companies that ask this question:
AmazonFacebookGoogleMicrosoftApple
LeetCode →NeetCode →

Approach

Binary Tree Maximum Path Sum

Problem Statement

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes 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

Input: root = [1,2,3]
Output: 6

Tree:
    1
   / \
  2   3

Max path: 2 → 1 → 3, sum = 6

Example 2

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

Tree:
      -10
      /  \
     9   20
        /  \
       15   7

Max path: 15 → 20 → 7, sum = 42

Intuition

For each node, the maximum path sum through that node can be:

  1. Node only
  2. Node + left path
  3. Node + right path
  4. Node + left path + right path (forms inverted V)

Key insight: A path through a node = node + max_left_path + max_right_path

But when returning to parent, we can only include ONE branch (either left or right), not both!

Two values to track:

  • Local max: max path sum through current node (can use both children)
  • Path max to parent: max path sum extending from current node upward (can use only one child)

Pattern Recognition

This is a Tree DFS + Global Maximum problem:

  • Post-order traversal (process children first)
  • Track global maximum
  • Return different value than what we track

Approach

DFS with Global Maximum

  1. Global Variable: max_sum = -infinity

  2. DFS Function: Returns max path sum extending from node (can go up to parent)

    def max_gain(node):
  if not node: return 0

  # Get max path sum from children (ignore negative paths)
  left_gain = max(max_gain(node.left), 0)
  right_gain = max(max_gain(node.right), 0)

  # Check if path through this node is better
  path_sum = node.val + left_gain + right_gain
  max_sum = max(max_sum, path_sum)

  # Return max path extending to parent (only one branch)
  return node.val + max(left_gain, right_gain)

  3. Key Points:

    • Use max(gain, 0) to ignore negative paths
    • Update global max with full path (both children)
    • Return to parent with only one child

Edge Cases

  • Single node
  • All negative values
  • Path is a single node
  • Path doesn't include root
  • Negative nodes in path

Complexity Analysis

  • Time: O(n) where n = number of nodes

    • Visit each node once
    • O(1) work per node

  • Space: O(h) where h = height

    • Recursion call stack
    • O(log n) for balanced tree
    • O(n) for skewed tree

Solution

java
1class TreeNode {
2    int val;
3    TreeNode left;
4    TreeNode right;
5    TreeNode() {}
6    TreeNode(int val) { this.val = val; }
7    TreeNode(int val, TreeNode left, TreeNode right) {
8        this.val = val;
9        this.left = left;
10        this.right = right;
11    }
12}
13
14class Solution {
15    private int maxSum = Integer.MIN_VALUE;
16
17    public int maxPathSum(TreeNode root) {
18        maxGain(root);
19        return maxSum;
20    }
21
22    private int maxGain(TreeNode node) {
23        if (node == null) {
24            return 0;
25        }
26
27        // Recursively get max path sum from children
28        // Use Math.max(gain, 0) to ignore negative paths
29        int leftGain = Math.max(maxGain(node.left), 0);
30        int rightGain = Math.max(maxGain(node.right), 0);
31
32        // Check if path through current node is new maximum
33        int pathSum = node.val + leftGain + rightGain;
34        maxSum = Math.max(maxSum, pathSum);
35
36        // Return max path sum extending from this node upward
37        // Can only use one branch when extending to parent
38        return node.val + Math.max(leftGain, rightGain);
39    }
40}
41
Loading visualizer...