Binary Tree Maximum Path Sum

February 22, 2026
Hard link_2
Take a look at the related concept first to better understand the problem
Tree Traversal

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.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Examples

Solution

Points of Interest

  1. This is a tree traversal problem using recursion.
  2. Here we can break a big tree into smaller trees and try to solve for them.
  3. Then we can combine the outputs from smaller trees to get max path sum of our bigger tree.
  4. If such a sub tree is just a single leaf node, then its max path sum will be its value itself.
  5. Now, if we focus on how we can join results from right and left sub tree, the following holds true.
    1. In a sub tree at a node, the max path sum could either be in its left sub tree, right sub tree or it could be passing through the node itself.
    2. Max path sum in right and left sub tree is already calculated by its child recursions.
    3. For a max path sum of this sub tree, we can calculate it using left and right max rooted path sum that ends at the left and right child respectively.
    4. Remember that left and right max rooted path sum should preferably be ≥0\geq{0}, as it’s better to include nothing from either side than to include negative value

Max rooted path sum is the sum of nodes of a binary tree that have one end at the root node of tree

Algo

The type of traversal we will be using is called Post-order traversal.

  1. Initialize a global variable called result with root.val as the initial value
  2. Create a recursive function _maxPathSum which takes root of a sub-tree as input and returns max rooted path sum of that sub-tree. Condition is that the max sum path should end at the root of this sub-tree
  3. If root is null, return 0
  4. Get max rooted path sum of left and right sub-trees and ensure that the value is either 0 or a positive integer
  5. Update the global variable with max value of itself or (max rooted path sum of left sub-tree + max rooted path sum of right sub-tree + value of root of this sub-tree)
  6. Then return max rooted path sum of this sub-tree itself, that will be (root value + max(max rooted path sum of left sub-tree, max rooted path sum of right sub-tree) )
  7. At the end of the recursion we will have our max path sum in our global variable.

Code

def maxPathSum(root: Optional[TreeNode]) -> int:
    res = root.val

    def _maxPathSum(node: Optional[TreeNode]) -> tuple[int, int]:
        nonlocal res
        if node is None:
            return 0
        
        l = max(0, _maxPathSum(node.left))
        r = max(0, _maxPathSum(node.right))
        res = max(res, l + r + node.val)

        return node.val + max(l, r)

    _ = _maxPathSum(root)
    return res

Complexity

Time Complexity=O(N) where N is the number of nodes in the binary tree\textbf{Time Complexity} = O(N) \text{ where N is the number of nodes in the binary tree}

Space Complexity=O(H) where H is the height of the binary tree\textbf{Space Complexity} = O(H) \text{ where H is the height of the binary tree}