Maximum Path Sum in Binary Tree in DSA Python - Build from Scratch

Maximum Path Sum in Binary Tree

📖 Scenario: Imagine you are working with a tree of numbers representing different paths in a park. Each node is a checkpoint with a score. You want to find the path through the park that gives the highest total score. This path can start and end at any checkpoint but must follow the tree connections.

🎯 Goal: Build a program to find the maximum path sum in a binary tree. You will create the tree, set up a helper variable, write the logic to find the maximum path sum, and finally print the result.

📋 What You'll Learn

Create a binary tree with the exact nodes and structure given

Use a helper variable to track the maximum path sum during traversal

Implement a recursive function to compute the maximum path sum

Print the maximum path sum after processing the tree

💡 Why This Matters

🌍 Real World

Finding maximum path sums in trees is useful in network routing, decision trees, and analyzing hierarchical data where the best path or combination is needed.

💼 Career

Understanding tree traversal and recursion is essential for software engineering roles, especially those involving algorithms, data analysis, and system design.

1

Create the Binary Tree Nodes

Create a class called TreeNode with an __init__ method that takes val, left, and right parameters. Then create the binary tree with these exact nodes and structure:
root = TreeNode(1), root.left = TreeNode(2), root.right = TreeNode(3), root.left.left = TreeNode(4), root.left.right = TreeNode(5), root.right.right = TreeNode(6)

DSA Python

# Define TreeNode class and create the tree nodes as described
# Your code here

Hint

Define the TreeNode class first. Then create the root node with value 1. Add left and right children as described.

2

Set Up a Helper Variable for Maximum Path Sum

Create a variable called max_sum and set it to float('-inf') to hold the maximum path sum found during traversal.

DSA Python

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

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

# Create max_sum variable to track maximum path sum
# Your code here

Hint

Use float('-inf') to start with the smallest possible number.

3

Implement Recursive Function to Find Maximum Path Sum

Define a function called max_gain that takes a node parameter. Inside, if node is None, return 0. Recursively call max_gain on node.left and node.right and store results in left_gain and right_gain. Use max(0, ...) to ignore negative gains. Calculate price_newpath as node.val + left_gain + right_gain. Update the global max_sum if price_newpath is greater. Return node.val + max(left_gain, right_gain).

DSA Python

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

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

max_sum = float('-inf')

# Define max_gain function to compute max path sum
# Your code here

Hint

Use recursion to explore left and right children. Use max(0, ...) to ignore negative paths. Update max_sum if a better path is found.

4

Print the Maximum Path Sum

Write a print statement to display the value of max_sum.

DSA Python

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

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

max_sum = float('-inf')

def max_gain(node):
    global max_sum
    if node is None:
        return 0
    left_gain = max(max_gain(node.left), 0)
    right_gain = max(max_gain(node.right), 0)
    price_newpath = node.val + left_gain + right_gain
    if price_newpath > max_sum:
        max_sum = price_newpath
    return node.val + max(left_gain, right_gain)

max_gain(root)

# Print the maximum path sum
# Your code here

Hint

Just print the max_sum variable after calling max_gain(root).

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