HardBlind75TreeDFS

Binary Tree Maximum Path Sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge. Return the maximum path sum of any non-empty path.

Examples

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

The maximum path sum is 2 -> 1 -> 3 with sum 6.

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

The maximum path sum is 15 -> 20 -> 7 with sum 42.

Constraints

  • •The number of nodes in the tree is in the range [1, 3 * 10^4]
  • •-1000 <= Node.val <= 1000

Approaches

Compute all possible paths and find the maximum sum.

CodeT: O(n^2) | S: O(h)
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_path_sum(root):
    max_sum = float('-inf')
    def dfs(node):
        nonlocal max_sum
        if not node:
            return 0
        left = max(dfs(node.left), 0)
        right = max(dfs(node.right), 0)
        max_sum = max(max_sum, node.val + left + right)
        return node.val + max(left, right)
    dfs(root)
    return max_sum

Use DFS to compute max gain from each node while tracking global max.

CodeT: O(n) | S: O(h)
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_path_sum(root):
    max_sum = float('-inf')
    def dfs(node):
        nonlocal max_sum
        if not node:
            return 0
        left = max(dfs(node.left), 0)
        right = max(dfs(node.right), 0)
        max_sum = max(max_sum, node.val + left + right)
        return node.val + max(left, right)
    dfs(root)
    return max_sum

Same approach with cleaner implementation.

Diagram

Tree: -10->9, 20->15,7 DFS: 9->0, 0->0, 15->0, 0->0 20: max_sum = max(-inf, 20+15+7) = 42 -10: max_sum = max(42, -10+20+0) = 42
CodeT: O(n) | S: O(h)
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_path_sum(root):
    self.max_sum = float('-inf')
    def dfs(node):
        if not node:
            return 0
        left = max(dfs(node.left), 0)
        right = max(dfs(node.right), 0)
        self.max_sum = max(self.max_sum, node.val + left + right)
        return node.val + max(left, right)
    dfs(root)
    return self.max_sum

Complexity Comparison

Brute Force - All Paths
T: O(n^2)S: O(h)

Compute all possible paths and find the maximum sum.

DFS with Global Max
T: O(n)S: O(h)

Use DFS to compute max gain from each node while tracking global max.

Optimized DFS
T: O(n)S: O(h)

Same approach with cleaner implementation.

Common Mistakes

Not ignoring negative contributions from children (max with 0)

Forgetting that the path can start and end at any node

Trying to return the path sum instead of the max gain from a subtree

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems