Binary Tree Maximum Path Sum

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. Return the maximum path sum of any non-empty path.

What to notice first

• Paths do not need to start or end at the root.
• A path can bend at a node (left + node + right).
• Negative gains from subtrees should be rejected (use max(0, gain)).

Examples

Input	Output	Path
[1,2,3]	6	2 → 1 → 3
[-10,9,20,null,null,15,7]	42	15 → 20 → 7

Constraints

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

Real-World Applications

Where this pattern appears

• File system hierarchies and directory structures
• DOM tree manipulation in web browsers
• XML/JSON parsing and configuration management
• Organizational hierarchies and permission trees

Complexity Comparison

Approach	Time	Space	Best When
Post-Order DFS + list tracking	O(n)	O(h)	Explicit max_sum storage
DFS with reference parameter	O(n)	O(h)	Cleaner max tracking

Approach 1: Post-Order DFS with List

★ Recommended

Use post-order DFS. At each node, compute max path through it and update global max. Return max single-path gain.

⏱ Time O(n) Visit each node once 💾 Space O(h) Recursion depth

Solution Code

Python

binary_tree_maximum_path_sum_postorder_dfs.py

from typing import Optional


# 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


def maxPathSum(root: Optional[TreeNode]) -> int:
    """
    Find maximum path sum in binary tree using post-order DFS.
    A path can pass through any node (not just root to leaf).
    Time: O(n), Space: O(h) for recursion stack
    """
    max_sum = [float('-inf')]

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

        # Max gain from left and right subtrees (at least 0 if negative)
        left_gain = max(0, dfs(node.left))
        right_gain = max(0, dfs(node.right))

        # Max path through this node (may bend at this node)
        max_path_through_node = node.val + left_gain + right_gain
        max_sum[0] = max(max_sum[0], max_path_through_node)

        # Return max path extending downward from this node
        return node.val + max(left_gain, right_gain)

    dfs(root)
    return max_sum[0]


# Test cases
if __name__ == "__main__":
    # Example 1: [1,2,3]
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)

    print(maxPathSum(root))  # 6 (path: 2 -> 1 -> 3)

    # Example 2: [-10,9,20,null,null,15,7]
    root2 = TreeNode(-10)
    root2.left = TreeNode(9)
    root2.right = TreeNode(20)
    root2.right.left = TreeNode(15)
    root2.right.right = TreeNode(7)

    print(maxPathSum(root2))  # 42 (path: 15 -> 20 -> 7)

    # Example 3: Single negative node
    single = TreeNode(-3)
    print(maxPathSum(single))  # -3

C++

binary_tree_maximum_path_sum_postorder_dfs.cpp

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    long long max_sum = LLONG_MIN;

    long long dfs(TreeNode* node) {
        if (!node) return 0;

        // Max gain from left and right subtrees (at least 0 if negative)
        long long left_gain = max(0LL, dfs(node->left));
        long long right_gain = max(0LL, dfs(node->right));

        // Max path through this node (may bend at this node)
        long long max_path_through_node = node->val + left_gain + right_gain;
        max_sum = max(max_sum, max_path_through_node);

        // Return max path extending downward from this node
        return node->val + max(left_gain, right_gain);
    }

public:
    int maxPathSum(TreeNode* root) {
        /**
         * Find maximum path sum in binary tree using post-order DFS.
         * A path can pass through any node (not just root to leaf).
         * Time: O(n), Space: O(h) for recursion stack
         */
        dfs(root);
        return (int)max_sum;
    }
};

// Test cases
int main() {
    // Example 1: [1,2,3]
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);

    Solution sol;
    cout << "Example 1 max path: " << sol.maxPathSum(root) << endl;  // 6 (2 -> 1 -> 3)

    // Example 2: [-10,9,20,null,null,15,7]
    TreeNode* root2 = new TreeNode(-10);
    root2->left = new TreeNode(9);
    root2->right = new TreeNode(20);
    root2->right->left = new TreeNode(15);
    root2->right->right = new TreeNode(7);

    Solution sol2;
    cout << "Example 2 max path: " << sol2.maxPathSum(root2) << endl;  // 42 (15 -> 20 -> 7)

    return 0;
}

Java

BinaryTreeMaximumPathSumPostorderDFS.java

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;

        int leftGain = Math.max(0, dfs(node.left));
        int rightGain = Math.max(0, dfs(node.right));

        int maxPathThroughNode = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, maxPathThroughNode);

        return node.val + Math.max(leftGain, rightGain);
    }
}

System.out.println(new Solution().maxPathSum(new TreeNode(1, new TreeNode(2), new TreeNode(3))));

JavaScript

binary_tree_maximum_path_sum_postorder_dfs.js

/**
 * Definition for a binary tree node.
 */
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * Find maximum path sum in binary tree using post-order DFS.
 * A path can pass through any node (not just root to leaf).
 * Time: O(n), Space: O(h) for recursion stack
 * @param {TreeNode} root
 * @return {number}
 */
function maxPathSum(root) {
    let maxSum = Number.MIN_SAFE_INTEGER;

    function dfs(node) {
        if (!node) return 0;

        // Max gain from left and right subtrees (at least 0 if negative)
        const leftGain = Math.max(0, dfs(node.left));
        const rightGain = Math.max(0, dfs(node.right));

        // Max path through this node (may bend at this node)
        const maxPathThroughNode = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, maxPathThroughNode);

        // Return max path extending downward from this node
        return node.val + Math.max(leftGain, rightGain);
    }

    dfs(root);
    return maxSum;
}

// Test cases
const root1 = new TreeNode(1);
root1.left = new TreeNode(2);
root1.right = new TreeNode(3);

console.log("Example 1 max path:", maxPathSum(root1));  // 6 (2 -> 1 -> 3)

const root2 = new TreeNode(-10);
root2.left = new TreeNode(9);
root2.right = new TreeNode(20);
root2.right.left = new TreeNode(15);
root2.right.right = new TreeNode(7);

console.log("Example 2 max path:", maxPathSum(root2));  // 42 (15 -> 20 -> 7)

Rust

binary_tree_maximum_path_sum_postorder_dfs.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/**
 * Find maximum path sum in binary tree using post-order DFS.
 * A path can pass through any node (not just root to leaf).
 * Time: O(n), Space: O(h) for recursion stack
 */
pub fn max_path_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    let mut max_sum = i64::MIN;
    dfs(root, &mut max_sum);
    max_sum as i32
}

fn dfs(node: Option<Rc<RefCell<TreeNode>>>, max_sum: &mut i64) -> i64 {
    match node {
        None => 0,
        Some(n) => {
            let node_ref = n.borrow();
            let val = node_ref.val as i64;
            let left = node_ref.left.clone();
            let right = node_ref.right.clone();
            drop(node_ref);

            // Max gain from left and right subtrees (at least 0 if negative)
            let left_gain = dfs(left, max_sum).max(0);
            let right_gain = dfs(right, max_sum).max(0);

            // Max path through this node (may bend at this node)
            let max_path_through_node = val + left_gain + right_gain;
            *max_sum = (*max_sum).max(max_path_through_node);

            // Return max path extending downward from this node
            val + left_gain.max(right_gain)
        }
    }
}

fn main() {
    println!("Example 1: Binary tree maximum path sum with DFS");
}

Go

binary_tree_maximum_path_sum_postorder_dfs.go

package main

import (
    "fmt"
    "math"
)

/**
 * Definition for a binary tree node.
 */
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

/**
 * Find maximum path sum in binary tree using post-order DFS.
 * A path can pass through any node (not just root to leaf).
 * Time: O(n), Space: O(h) for recursion stack
 */
func maxPathSum(root *TreeNode) int {
    maxSum := math.MinInt
    dfs(root, &maxSum)
    return maxSum
}

func dfs(node *TreeNode, maxSum *int) int64 {
    if node == nil {
        return 0
    }

    // Max gain from left and right subtrees (at least 0 if negative)
    leftGain := max(0, dfs(node.Left, maxSum))
    rightGain := max(0, dfs(node.Right, maxSum))

    // Max path through this node (may bend at this node)
    maxPathThroughNode := int64(node.Val) + leftGain + rightGain
    *maxSum = max(*maxSum, int(maxPathThroughNode))

    // Return max path extending downward from this node
    return int64(node.Val) + max(leftGain, rightGain)
}

func max(a, b int64) int64 {
    if a > b {
        return a
    }
    return b
}

func main() {
    fmt.Println("Example 1: Binary tree maximum path sum with DFS")
}

Approach 2: DFS with Reference Max Tracking

alternative

Pass max_sum as mutable reference. Update during traversal. Same logic, different max tracking style.

⏱ Time O(n) Visit each node once 💾 Space O(h) Recursion depth

Solution Code

Python

binary_tree_maximum_path_sum_dfs_max_tracking.py

from typing import Optional


# 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


class Solution:
    def __init__(self):
        self.max_sum = float('-inf')

    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        """
        Find maximum path sum using DFS with class-level max tracking.
        Maintains max_sum as instance variable updated during traversal.
        Time: O(n), Space: O(h) for recursion stack
        """
        def dfs(node):
            if not node:
                return 0

            # Max single-path sum extending from this node
            left_sum = max(0, dfs(node.left))
            right_sum = max(0, dfs(node.right))

            # Path bending at this node
            path_sum = node.val + left_sum + right_sum
            self.max_sum = max(self.max_sum, path_sum)

            # Return best single path extending downward
            return node.val + max(left_sum, right_sum)

        dfs(root)
        return self.max_sum


# Test cases
if __name__ == "__main__":
    # Example 1: [1,2,3]
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)

    sol = Solution()
    print(sol.maxPathSum(root))  # 6 (path: 2 -> 1 -> 3)

    # Example 2: [-10,9,20,null,null,15,7]
    root2 = TreeNode(-10)
    root2.left = TreeNode(9)
    root2.right = TreeNode(20)
    root2.right.left = TreeNode(15)
    root2.right.right = TreeNode(7)

    sol2 = Solution()
    print(sol2.maxPathSum(root2))  # 42 (path: 15 -> 20 -> 7)

    # Example 3: Single negative node
    single = TreeNode(-3)
    sol3 = Solution()
    print(sol3.maxPathSum(single))  # -3

C++

binary_tree_maximum_path_sum_dfs_max_tracking.cpp

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        /**
         * Find maximum path sum using DFS with class-level max tracking.
         * Maintains max_sum as instance variable updated during traversal.
         * Time: O(n), Space: O(h) for recursion stack
         */
        long long max_sum = LLONG_MIN;
        dfs(root, max_sum);
        return (int)max_sum;
    }

private:
    long long dfs(TreeNode* node, long long& max_sum) {
        if (!node) return 0;

        // Max single-path sum extending from this node
        long long left_sum = max(0LL, dfs(node->left, max_sum));
        long long right_sum = max(0LL, dfs(node->right, max_sum));

        // Path bending at this node
        long long path_sum = node->val + left_sum + right_sum;
        max_sum = max(max_sum, path_sum);

        // Return best single path extending downward
        return node->val + max(left_sum, right_sum);
    }
};

// Test cases
int main() {
    // Example 1: [1,2,3]
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);

    Solution sol;
    cout << "Example 1 max path: " << sol.maxPathSum(root) << endl;  // 6 (2 -> 1 -> 3)

    // Example 2: [-10,9,20,null,null,15,7]
    TreeNode* root2 = new TreeNode(-10);
    root2->left = new TreeNode(9);
    root2->right = new TreeNode(20);
    root2->right->left = new TreeNode(15);
    root2->right->right = new TreeNode(7);

    Solution sol2;
    cout << "Example 2 max path: " << sol2.maxPathSum(root2) << endl;  // 42 (15 -> 20 -> 7)

    return 0;
}

Java

BinaryTreeMaximumPathSumDFSMaxTracking.java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    /**
     * Find maximum path sum using DFS with mutable max tracking.
     * Maintains maxSum as instance variable updated during traversal.
     * Time: O(n), Space: O(h) for recursion stack
     */
    public int maxPathSum(TreeNode root) {
        long[] maxSum = {Long.MIN_VALUE};
        dfs(root, maxSum);
        return (int)maxSum[0];
    }

    private long dfs(TreeNode node, long[] maxSum) {
        if (node == null) return 0;

        // Max single-path sum extending from this node
        long leftSum = Math.max(0L, dfs(node.left, maxSum));
        long rightSum = Math.max(0L, dfs(node.right, maxSum));

        // Path bending at this node
        long pathSum = node.val + leftSum + rightSum;
        maxSum[0] = Math.max(maxSum[0], pathSum);

        // Return best single path extending downward
        return node.val + Math.max(leftSum, rightSum);
    }
}

class Main {
    public static void main(String[] args) {
        // Example 1: [1,2,3]
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        Solution sol = new Solution();
        System.out.println("Example 1 max path: " + sol.maxPathSum(root));  // 6 (2 -> 1 -> 3)

        // Example 2: [-10,9,20,null,null,15,7]
        TreeNode root2 = new TreeNode(-10);
        root2.left = new TreeNode(9);
        root2.right = new TreeNode(20);
        root2.right.left = new TreeNode(15);
        root2.right.right = new TreeNode(7);

        Solution sol2 = new Solution();
        System.out.println("Example 2 max path: " + sol2.maxPathSum(root2));  // 42 (15 -> 20 -> 7)
    }
}

JavaScript

binary_tree_maximum_path_sum_dfs_max_tracking.js

/**
 * Definition for a binary tree node.
 */
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * Find maximum path sum using DFS with mutable max tracking.
 * Maintains maxSum as variable updated during traversal.
 * Time: O(n), Space: O(h) for recursion stack
 * @param {TreeNode} root
 * @return {number}
 */
function maxPathSum(root) {
    const maxSum = [Number.MIN_SAFE_INTEGER];

    function dfs(node) {
        if (!node) return 0;

        // Max single-path sum extending from this node
        const leftSum = Math.max(0, dfs(node.left));
        const rightSum = Math.max(0, dfs(node.right));

        // Path bending at this node
        const pathSum = node.val + leftSum + rightSum;
        maxSum[0] = Math.max(maxSum[0], pathSum);

        // Return best single path extending downward
        return node.val + Math.max(leftSum, rightSum);
    }

    dfs(root);
    return maxSum[0];
}

// Test cases
const root1 = new TreeNode(1);
root1.left = new TreeNode(2);
root1.right = new TreeNode(3);

console.log("Example 1 max path:", maxPathSum(root1));  // 6 (2 -> 1 -> 3)

const root2 = new TreeNode(-10);
root2.left = new TreeNode(9);
root2.right = new TreeNode(20);
root2.right.left = new TreeNode(15);
root2.right.right = new TreeNode(7);

console.log("Example 2 max path:", maxPathSum(root2));  // 42 (15 -> 20 -> 7)

Rust

binary_tree_maximum_path_sum_dfs_max_tracking.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/**
 * Find maximum path sum using DFS with mutable max tracking.
 * Maintains maxSum as mutable reference updated during traversal.
 * Time: O(n), Space: O(h) for recursion stack
 */
pub fn max_path_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    let mut max_sum = i64::MIN;
    dfs(root, &mut max_sum);
    max_sum as i32
}

fn dfs(node: Option<Rc<RefCell<TreeNode>>>, max_sum: &mut i64) -> i64 {
    match node {
        None => 0,
        Some(n) => {
            let node_ref = n.borrow();
            let val = node_ref.val as i64;
            let left = node_ref.left.clone();
            let right = node_ref.right.clone();
            drop(node_ref);

            // Max single-path sum extending from this node
            let left_sum = dfs(left, max_sum).max(0);
            let right_sum = dfs(right, max_sum).max(0);

            // Path bending at this node
            let path_sum = val + left_sum + right_sum;
            *max_sum = (*max_sum).max(path_sum);

            // Return best single path extending downward
            val + left_sum.max(right_sum)
        }
    }
}

fn main() {
    println!("Example 1: Binary tree maximum path sum with max tracking");
}

Go

binary_tree_maximum_path_sum_dfs_max_tracking.go

package main

import (
    "fmt"
    "math"
)

/**
 * Definition for a binary tree node.
 */
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

/**
 * Find maximum path sum using DFS with max tracking.
 * Maintains maxSum as mutable reference updated during traversal.
 * Time: O(n), Space: O(h) for recursion stack
 */
func maxPathSum(root *TreeNode) int {
    maxSum := math.MinInt
    dfs(root, &maxSum)
    return maxSum
}

func dfs(node *TreeNode, maxSum *int) int64 {
    if node == nil {
        return 0
    }

    // Max single-path sum extending from this node
    leftSum := maxInt64(0, dfs(node.Left, maxSum))
    rightSum := maxInt64(0, dfs(node.Right, maxSum))

    // Path bending at this node
    pathSum := int64(node.Val) + leftSum + rightSum
    *maxSum = max(*maxSum, int(pathSum))

    // Return best single path extending downward
    return int64(node.Val) + maxInt64(leftSum, rightSum)
}

func maxInt64(a, b int64) int64 {
    if a > b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    fmt.Println("Example 1: Binary tree maximum path sum with max tracking")
}

Related Problems

• Path Sum ↗ Easy #112
• Sum Root to Leaf Numbers ↗ Medium #129
• Diameter of Binary Tree ↗ Easy #543

Interview Tips

Key trade-offs to discuss

• Key insight: Return the max single-path gain, but track max path that may bend.
• Negative handling: Reject negative contributions with max(0, gain).
• Path bending: Only possible at each node (left + node + right).
• Edge cases: Single negative node, all negative tree, negative subtrees.

← Previous
#123 Best Time to Buy and Sell Stock III Next
#125 Valid Palindrome →