Binary Tree Maximum Path Sum

Description

A path in a binary tree is any sequence of nodes where each consecutive pair is connected by an edge. Unlike root-to-leaf paths, a path here can start and end at any node in the tree — it does not have to pass through the root, and it does not have to go downward. The only restriction is that each node can appear at most once in the path.

The path sum is the sum of all node values along the path. Given the root of a binary tree, your task is to find the maximum path sum among all possible non-empty paths in the tree.

Note that node values can be negative, which makes this problem more challenging. A path might deliberately avoid certain subtrees if their contribution would decrease the total sum.

A binary tree with root -10, left child 9, right child 20 with children 15 and 7. The optimal path 15 → 20 → 7 is highlighted in green, showing sum 42.

Examples

Example 1

Input: root = [1, 2, 3]

Output: 6

Explanation: The tree has root 1, left child 2, and right child 3. The path that goes 2 → 1 → 3 passes through the root and includes both children. The sum is 2 + 1 + 3 = 6. This is the maximum because every other path (just node 1 = 1, just node 2 = 2, just node 3 = 3, path 2 → 1 = 3, path 1 → 3 = 4) has a smaller sum.

Example 2

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

Output: 42

Explanation: The tree has root -10, left child 9, and right child 20 with children 15 and 7. The optimal path is 15 → 20 → 7 with sum 15 + 20 + 7 = 42. Notice this path does not include the root (-10) because including it would decrease the sum. The path through the root (9 → -10 → 20 → 15 = 34, or 9 → -10 → 20 → 7 = 26) is worse because the -10 drags the sum down. The algorithm must consider that skipping the root can be optimal.

Example 3

Input: root = [-3]

Output: -3

Explanation: The tree has only one node with value -3. Even though the value is negative, the problem requires a non-empty path, so we must include at least one node. The maximum path sum is -3.

Constraints

The number of nodes in the tree is in the range [1, 3 × 10^4]
-1000 ≤ Node.val ≤ 1000

Editorial

Brute Force

Intuition

The most straightforward approach is to consider every possible pair of nodes in the tree and compute the path sum between them. A path between any two nodes in a binary tree is unique (there is exactly one path connecting them via their lowest common ancestor). We find the path between every pair, calculate its sum, and track the global maximum.

Think of it like a hiking trail network shaped like a tree. You want to find the most scenic route (highest total elevation score) between any two trailheads. You could exhaustively try every pair of trailheads, walk between them, add up all the elevation scores along the way, and remember the best one.

To implement this, for each pair of nodes (u, v), we find their lowest common ancestor (LCA), then sum the path from u up to the LCA plus the path from the LCA down to v. Since there are O(n²) pairs and finding the LCA and path sum takes O(n) in the worst case, this approach is very slow.

Step-by-Step Explanation

Let's trace through with the tree root = [1, 2, 3] (root 1, left child 2, right child 3):

Step 1: Enumerate all nodes: {1, 2, 3}. We need to check all paths — both single-node paths and multi-node paths.

Step 2: Single-node paths: node 1 → sum = 1. Node 2 → sum = 2. Node 3 → sum = 3. Best so far: 3.

Step 3: Path between nodes 1 and 2: LCA is 1. Path is 2 → 1. Sum = 2 + 1 = 3. Best so far: 3.

Step 4: Path between nodes 1 and 3: LCA is 1. Path is 1 → 3. Sum = 1 + 3 = 4. Best so far: 4.

Step 5: Path between nodes 2 and 3: LCA is 1. Path is 2 → 1 → 3. Sum = 2 + 1 + 3 = 6. Best so far: 6.

Step 6: All pairs examined. Return maximum = 6.

Algorithm

Collect all nodes in the tree into a list
For every pair of nodes (u, v) including u == v (single-node paths):
a. Find their lowest common ancestor (LCA)
b. Compute the sum of values on the path from u to LCA to v
c. Update the global maximum if this sum is larger
Return the global maximum

Code

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        vector<TreeNode*> nodes;
        collectNodes(root, nodes);
        
        int maxSum = INT_MIN;
        for (auto u : nodes) {
            for (auto v : nodes) {
                int pathSum = getPathSum(root, u, v);
                maxSum = max(maxSum, pathSum);
            }
        }
        return maxSum;
    }
    
private:
    void collectNodes(TreeNode* node, vector<TreeNode*>& nodes) {
        if (!node) return;
        nodes.push_back(node);
        collectNodes(node->left, nodes);
        collectNodes(node->right, nodes);
    }
    
    TreeNode* findLCA(TreeNode* root, TreeNode* u, TreeNode* v) {
        if (!root || root == u || root == v) return root;
        TreeNode* left = findLCA(root->left, u, v);
        TreeNode* right = findLCA(root->right, u, v);
        if (left && right) return root;
        return left ? left : right;
    }
    
    int pathToNode(TreeNode* root, TreeNode* target, int sum) {
        if (!root) return INT_MIN;
        if (root == target) return sum + root->val;
        int left = pathToNode(root->left, target, sum + root->val);
        int right = pathToNode(root->right, target, sum + root->val);
        return (left != INT_MIN) ? left : right;
    }
    
    int getPathSum(TreeNode* root, TreeNode* u, TreeNode* v) {
        TreeNode* lca = findLCA(root, u, v);
        int sumU = pathToNode(lca, u, 0);
        int sumV = pathToNode(lca, v, 0);
        return sumU + sumV - lca->val;
    }
};

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        nodes = []
        self._collect_nodes(root, nodes)
        
        max_sum = float('-inf')
        for u in nodes:
            for v in nodes:
                path_sum = self._get_path_sum(root, u, v)
                max_sum = max(max_sum, path_sum)
        return max_sum
    
    def _collect_nodes(self, node, nodes):
        if not node:
            return
        nodes.append(node)
        self._collect_nodes(node.left, nodes)
        self._collect_nodes(node.right, nodes)
    
    def _find_lca(self, root, u, v):
        if not root or root == u or root == v:
            return root
        left = self._find_lca(root.left, u, v)
        right = self._find_lca(root.right, u, v)
        if left and right:
            return root
        return left if left else right
    
    def _path_to_node(self, root, target, current_sum):
        if not root:
            return float('-inf')
        if root == target:
            return current_sum + root.val
        left = self._path_to_node(root.left, target, current_sum + root.val)
        right = self._path_to_node(root.right, target, current_sum + root.val)
        return left if left != float('-inf') else right
    
    def _get_path_sum(self, root, u, v):
        lca = self._find_lca(root, u, v)
        sum_u = self._path_to_node(lca, u, 0)
        sum_v = self._path_to_node(lca, v, 0)
        return sum_u + sum_v - lca.val

class Solution {
    public int maxPathSum(TreeNode root) {
        List<TreeNode> nodes = new ArrayList<>();
        collectNodes(root, nodes);
        
        int maxSum = Integer.MIN_VALUE;
        for (TreeNode u : nodes) {
            for (TreeNode v : nodes) {
                int pathSum = getPathSum(root, u, v);
                maxSum = Math.max(maxSum, pathSum);
            }
        }
        return maxSum;
    }
    
    private void collectNodes(TreeNode node, List<TreeNode> nodes) {
        if (node == null) return;
        nodes.add(node);
        collectNodes(node.left, nodes);
        collectNodes(node.right, nodes);
    }
    
    private TreeNode findLCA(TreeNode root, TreeNode u, TreeNode v) {
        if (root == null || root == u || root == v) return root;
        TreeNode left = findLCA(root.left, u, v);
        TreeNode right = findLCA(root.right, u, v);
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }
    
    private int pathToNode(TreeNode root, TreeNode target, int sum) {
        if (root == null) return Integer.MIN_VALUE;
        if (root == target) return sum + root.val;
        int left = pathToNode(root.left, target, sum + root.val);
        int right = pathToNode(root.right, target, sum + root.val);
        return (left != Integer.MIN_VALUE) ? left : right;
    }
    
    private int getPathSum(TreeNode root, TreeNode u, TreeNode v) {
        TreeNode lca = findLCA(root, u, v);
        int sumU = pathToNode(lca, u, 0);
        int sumV = pathToNode(lca, v, 0);
        return sumU + sumV - lca.val;
    }
}

Complexity Analysis

Time Complexity: O(n³)

There are O(n²) pairs of nodes. For each pair, finding the LCA takes O(n) time and computing the path sum takes O(n) time. This gives O(n²) × O(n) = O(n³) total.

Space Complexity: O(n)

We store all n nodes in a list, and the recursion stack can go up to O(n) deep in a skewed tree.

Why This Approach Is Not Efficient

With up to 3 × 10^4 nodes, O(n³) means up to 2.7 × 10^13 operations — far too slow for any reasonable time limit. The approach does enormous redundant work: it considers every pair of nodes independently, even though many paths share common substructures.

The fundamental inefficiency is that we treat the tree as a flat collection of node pairs, ignoring the tree structure entirely. A smarter approach would exploit the fact that every path in a binary tree has a unique "turning point" — the highest node in the path. If we process each node as a potential turning point, we can compute the best path through that node in constant time per node (after preprocessing its subtrees), reducing the total work to O(n).

Key insight: instead of enumerating paths, we can use a post-order DFS where each node reports the best single-branch path sum coming up from its subtree. At each node, we combine the best left branch and best right branch (both clamped at zero to handle negatives) to get the best "through-path" at that node, and we update a global maximum.

Optimal Approach - DFS with Global Maximum

Intuition

The key insight is that every path in a binary tree passes through exactly one "highest" node — the node closest to the root on that path. At this highest node, the path either goes only through one subtree (a single-arm path), or it connects the left subtree to the right subtree through the node (a two-arm path).

Imagine standing at any node in the tree with your arms stretched out. Your left arm reaches down into the left subtree collecting the best chain of values it can find. Your right arm does the same for the right subtree. The total path sum through you is: left arm + your value + right arm. If either arm would collect a negative sum, you simply retract it (clamp to zero) because including a negative contribution would only hurt.

We perform a post-order DFS (process children before parent). At each node, we:

Recursively compute the best single-arm path sum from the left subtree
Recursively compute the best single-arm path sum from the right subtree
Clamp each to zero (ignoring negative contributions)
Update the global maximum with: left_arm + node.val + right_arm (the best path THROUGH this node)
Return node.val + max(left_arm, right_arm) upward to the parent — because a path can only continue in one direction when extending upward

The distinction between step 4 and step 5 is critical: when a node acts as the turning point, it can use BOTH arms. But when reporting upward to its parent, it can only extend along ONE arm (otherwise the path would fork, which is not allowed).

Step-by-Step Explanation

Let's trace through with root = [-10, 9, 20, null, null, 15, 7]:

The tree looks like:

Step 1: DFS visits node 9 (leaf). Left arm = 0 (no left child), right arm = 0 (no right child). Through-path = 0 + 9 + 0 = 9. Update global max = 9. Return 9 + max(0, 0) = 9 upward.

Step 2: DFS visits node 15 (leaf). Left arm = 0, right arm = 0. Through-path = 0 + 15 + 0 = 15. Update global max = 15. Return 15 upward.

Step 3: DFS visits node 7 (leaf). Left arm = 0, right arm = 0. Through-path = 0 + 7 + 0 = 7. Global max stays 15. Return 7 upward.

Step 4: DFS visits node 20. Left arm = 15 (from step 2), right arm = 7 (from step 3). Both are positive, so no clamping needed. Through-path = 15 + 20 + 7 = 42. Update global max = 42. Return 20 + max(15, 7) = 20 + 15 = 35 upward. We can only extend one arm when going up — we pick the better one (15).

Step 5: DFS visits root -10. Left arm = 9 (from step 1), right arm = 35 (from step 4). Through-path = 9 + (-10) + 35 = 34. Global max stays 42 (34 < 42). Return -10 + max(9, 35) = -10 + 35 = 25 upward.

Step 6: DFS complete. Return global max = 42.

Binary Tree Maximum Path Sum — Post-Order DFS — Watch how DFS processes leaves first, then propagates the best single-arm path sum upward while tracking the global maximum through-path at each node.

Algorithm

Initialize a global variable maxSum = -∞
Define a recursive function dfs(node):
a. If node is null, return 0
b. Recursively call dfs(node.left) → leftGain, clamp to max(0, leftGain)
c. Recursively call dfs(node.right) → rightGain, clamp to max(0, rightGain)
d. Compute throughPath = leftGain + node.val + rightGain
e. Update maxSum = max(maxSum, throughPath)
f. Return node.val + max(leftGain, rightGain) — the best single-arm path from this subtree
Call dfs(root)
Return maxSum

Code

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int maxSum = INT_MIN;
        dfs(root, maxSum);
        return maxSum;
    }
    
private:
    int dfs(TreeNode* node, int& maxSum) {
        if (!node) return 0;
        
        // Get max gain from left and right subtrees
        // Clamp to 0: if a subtree contributes negative, ignore it
        int leftGain = max(0, dfs(node->left, maxSum));
        int rightGain = max(0, dfs(node->right, maxSum));
        
        // Path through this node using both arms
        int throughPath = leftGain + node->val + rightGain;
        maxSum = max(maxSum, throughPath);
        
        // Return single-arm path to parent
        return node->val + max(leftGain, rightGain);
    }
};

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.max_sum = float('-inf')
        
        def dfs(node):
            if not node:
                return 0
            
            # Get max gain from left and right subtrees
            # Clamp to 0: if a subtree contributes negative, ignore it
            left_gain = max(0, dfs(node.left))
            right_gain = max(0, dfs(node.right))
            
            # Path through this node using both arms
            through_path = left_gain + node.val + right_gain
            self.max_sum = max(self.max_sum, through_path)
            
            # Return single-arm path to parent
            return node.val + max(left_gain, right_gain)
        
        dfs(root)
        return self.max_sum

class Solution {
    private int maxSum;
    
    public int maxPathSum(TreeNode root) {
        maxSum = Integer.MIN_VALUE;
        dfs(root);
        return maxSum;
    }
    
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        
        // Get max gain from left and right subtrees
        // Clamp to 0: if a subtree contributes negative, ignore it
        int leftGain = Math.max(0, dfs(node.left));
        int rightGain = Math.max(0, dfs(node.right));
        
        // Path through this node using both arms
        int throughPath = leftGain + node.val + rightGain;
        maxSum = Math.max(maxSum, throughPath);
        
        // Return single-arm path to parent
        return node.val + Math.max(leftGain, rightGain);
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit each node exactly once during the post-order DFS. At each node, we do O(1) work: two recursive calls (counted separately), one addition, two max operations, and one comparison. The total work across all nodes is O(n).

Space Complexity: O(h) where h is the height of the tree

The space is used by the recursion call stack. In the worst case (a completely skewed tree), h = n, so space is O(n). In the best case (a balanced tree), h = log n, so space is O(log n). No additional data structures are needed beyond the recursion stack.

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

HARD

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Binary Tree Maximum Path Sum

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - DFS with Global Maximum

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis