Binary Tree Maximum Path Sum | Leetcode 124

Welcome to our deep dive on Binary Tree Maximum Path Sum (Leetcode 124). This is a classical Hard problem that perfectly demonstrates post-order traversal and updating global state during a DFS.

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 essentially once in the sequence. 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.

Example: 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.)

Approach: Post-Order DFS O(N)

Solving tree paths usually requires understanding what information must flow "up" to the parent, and what information is "global" to the whole tree.

A path can "split" exactly once at its highest peak. For example, a valid path could go up the left child, hit the current root node, and then go down the right child. This represents a complete local path: left_branch + root.val + right_branch.

However, the current root node cannot pass both of its branches up to its parent! If it did, it would form a Y-shape, which is not a valid line path. The root can only return a single straight line to its parent: root.val + max(left_branch, right_branch).

1. Use a global variable res (or array [res]) initialized to -infinity to track the absolute largest overall split path discovered.
2. Create our dfs function.
3. Recursively calculate left_branch = max(dfs(node.left), 0). We use max(..., 0) because if a branch yields a negative sum, we'd rather just ignore that entire branch entirely!
4. Recursively calculate right_branch = max(dfs(node.right), 0).
5. Update global total: res = max(res, node.val + left_branch + right_branch).
6. Return the straight line to the parent: return node.val + max(left_branch, right_branch).

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        res = [float('-inf')]
        
        def dfs(node):
            if not node: return 0
            
            # Max path sum from left and right children. Ignore negatives.
            left_max = max(dfs(node.left), 0)
            right_max = max(dfs(node.right), 0)
            
            # Compute max path sum WITH split at current node
            res[0] = max(res[0], node.val + left_max + right_max)
            
            # Return max path sum WITHOUT split
            return node.val + max(left_max, right_max)
            
        dfs(root)
        return res[0]

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (124)