Maximum Path Sum in Binary Tree in DSA Python

Mental Model

Find the highest sum of values along any path in a tree, where a path can start and end at any node.

Analogy: Imagine climbing a mountain range where each peak has a height. You want to find the highest total height you can get by walking along connected peaks, but you can start and stop anywhere.

      1
     / \
    2   3
   / \
  4   5

Dry Run Walkthrough

Input: Binary tree: 1 -> 2 -> 4, 2 -> 5, 1 -> 3

Goal: Find the maximum sum path anywhere in the tree

Step 1: Start at leaf node 4, max path sum from 4 is 4

4 (leaf) -> max path sum = 4

Why: Leaf nodes have max path sum equal to their own value

Step 2: At node 5, max path sum from 5 is 5

5 (leaf) -> max path sum = 5

Why: Leaf nodes have max path sum equal to their own value

Step 3: At node 2, calculate max path sum including left and right children: max(4,5) + 2 = 7, also consider path through node 2: 4 + 2 + 5 = 11

2 -> left=4, right=5, max single path=7, max path through node=11

Why: We consider max path going down one side and also path through node connecting both sides

Step 4: At node 3, max path sum is 3 (leaf)

3 (leaf) -> max path sum = 3

Why: Leaf node max path sum is its own value

Step 5: At root 1, calculate max path sum including children: max(7,3) + 1 = 8, also consider path through root: 7 + 1 + 3 = 11

1 -> left=7, right=3, max single path=8, max path through node=11

Why: Root can connect left and right max paths for a bigger sum

Result:

Maximum path sum is 11
Final max path: 4 -> 2 -> 5 or 4 -> 2 -> 1 -> 3 (both sum to 11)

Annotated Code

DSA Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.max_sum = float('-inf')

        def max_gain(node):
            if not node:
                return 0
            # max sum on the left and right, ignore negatives
            left_gain = max(max_gain(node.left), 0)
            right_gain = max(max_gain(node.right), 0)

            # price_newpath is sum through current node
            price_newpath = node.val + left_gain + right_gain

            # update max_sum if price_newpath is better
            self.max_sum = max(self.max_sum, price_newpath)

            # return max gain if continue path from current node
            return node.val + max(left_gain, right_gain)

        max_gain(root)
        return self.max_sum

# Driver code
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

sol = Solution()
print(sol.maxPathSum(root))

if not node: return 0

stop recursion at null nodes

left_gain = max(max_gain(node.left), 0) right_gain = max(max_gain(node.right), 0)

calculate max gain from left and right children ignoring negative sums

price_newpath = node.val + left_gain + right_gain

calculate sum if path passes through current node connecting left and right

self.max_sum = max(self.max_sum, price_newpath)

update global max sum if current path is better

return node.val + max(left_gain, right_gain)

return max gain continuing from current node to one child

Output

11

Complexity Analysis

Time: O(n) because we visit each node once in the tree

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Naive approach checking all paths would be O(n^2), this uses DFS with pruning for O(n)

Edge Cases

Tree with all negative values

Algorithm returns the least negative single node value as max path sum

DSA Python

left_gain = max(max_gain(node.left), 0)

Single node tree

Returns the value of the single node

DSA Python

if not node:
    return 0

Tree with zero values

Zero values are included if they increase path sum, otherwise ignored

DSA Python

left_gain = max(max_gain(node.left), 0)

When to Use This Pattern

When asked to find the maximum sum path in a tree that can start and end anywhere, use DFS with tracking max sums including both children to find the global max path.

Common Mistakes

Mistake: Returning sum of left and right children without ignoring negative sums
Fix: Use max(child_sum, 0) to ignore negative paths that reduce total

Mistake: Updating max sum only with paths that start at root
Fix: Update max sum at every node considering paths through that node

Summary

Finds the maximum sum of any path in a binary tree where path can start and end at any node.

Use when you need the highest sum path in a tree, not limited to root or leaves.

The key is to track max gain from children ignoring negatives and update global max with paths through each node.

Practice

1. What does the "maximum path sum" in a binary tree represent?

easy

A. The sum of values from root to the deepest leaf

B. The largest sum of values along any path between two nodes

C. The maximum value of a single node in the tree

D. The sum of all node values in the tree

Solution

1. Step 1: Understand the path definition

   A path can start and end at any nodes, not necessarily root or leaf.

2. Step 2: Define maximum path sum

   It is the highest sum of node values along any such path in the tree.

3. Final Answer:

   The largest sum of values along any path between two nodes -> Option B

4. Quick Check:

   Maximum path sum = largest sum on any path [OK]

Hint: Remember path can start/end anywhere, not just root or leaf [OK]

Common Mistakes:

• Thinking path must start at root
• Confusing max node value with max path sum
• Summing all nodes instead of a path

2. Which of the following Python function signatures is correct for a recursive helper to find maximum path sum in a binary tree node root?

easy

A. def maxPathSum(root: TreeNode) -> int:

B. def maxPathSum(root: int) -> TreeNode:

C. def maxPathSum(root: TreeNode) -> TreeNode:

D. def maxPathSum(root: int) -> int:

Solution

1. Step 1: Identify input type

   The function takes a TreeNode object representing the root of the tree.

2. Step 2: Identify return type

   The function returns an integer representing the maximum path sum.

3. Final Answer:

   def maxPathSum(root: TreeNode) -> int: -> Option A

4. Quick Check:

   Input=TreeNode, Output=int [OK]

Hint: Input is tree node, output is integer sum [OK]

Common Mistakes:

• Using int as input instead of TreeNode
• Returning TreeNode instead of int
• Mixing input and output types

3. Given the following binary tree and code snippet, what is the output?

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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

root = TreeNode(-10, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(maxPathSum(root))

medium

A. 35

B. 27

C. 42

D. 20

Solution

1. Step 1: Trace left and right subtree sums

   Left subtree max path sum is 9, right subtree max path sum is 20 + 15 + 7 = 42.

2. Step 2: Calculate max path sum including root

   Root (-10) + left (9) + right (20 + 15 + 7) = -10 + 9 + 22 = 21, but max path sum is updated at right subtree as 42.

3. Step 3: Identify maximum path sum

   The maximum path sum is 42, but the path that includes root is less than 42.

4. Final Answer:

   42 -> Option C

5. Quick Check:

   Max path sum = 42 [OK]

Hint: Add max(0, left/right) to avoid negative sums [OK]

Common Mistakes:

• Including negative sums from subtrees
• Confusing return value with max_sum
• Not using nonlocal for max_sum

4. Find the error in the following code snippet for maximum path sum in a binary tree:

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

medium

A. max_sum should be declared as nonlocal inside helper

B. Return statement should be outside helper function

C. Base case should return None instead of 0

D. max_sum should be initialized to 0 instead of -inf

Solution

1. Step 1: Identify variable scope issue

   max_sum is assigned inside helper but declared outside, so Python treats it as local inside helper.

2. Step 2: Fix scope with nonlocal keyword

   Adding 'nonlocal max_sum' inside helper allows updating the outer max_sum variable.

3. Final Answer:

   max_sum should be declared as nonlocal inside helper -> Option A

4. Quick Check:

   Use nonlocal to update outer variable [OK]

Hint: Use nonlocal to modify outer variables inside nested functions [OK]

Common Mistakes:

• Forgetting nonlocal causes UnboundLocalError
• Changing base case return value incorrectly
• Initializing max_sum to 0 misses negative sums

5. You want to find the maximum path sum in a binary tree where some nodes have negative values. Which approach correctly handles negative values to find the maximum path sum?

hard

A. Only consider paths starting at root to leaf

B. Add all child sums regardless of sign to current node value

C. Replace negative node values with zero before calculation

D. Ignore negative child sums by taking max(child_sum, 0) before adding to current node

Solution

1. Step 1: Understand impact of negative values

   Negative sums reduce total path sum, so ignoring them improves max sum.

2. Step 2: Use max(child_sum, 0) to ignore negatives

   This ensures only positive contributions add to current node's path sum.

3. Step 3: Avoid altering original node values

   Replacing negatives with zero changes tree data and is incorrect.

4. Final Answer:

   Ignore negative child sums by taking max(child_sum, 0) before adding to current node -> Option D

5. Quick Check:

   Ignore negatives with max(child_sum, 0) [OK]

Hint: Use max(child_sum, 0) to skip negative paths [OK]

Common Mistakes:

• Adding negative sums reduces max path sum
• Modifying node values instead of sums
• Restricting paths to root-leaf only