\

Binary Tree Maximum Path Sum

Difficulty: N/A | Solved: December 20, 2025

Problem

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.

Example 1:

Input: root = [1,2,3] Output: 6 Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: 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.

Brainstorming

Brute force

So if i understand currently we need to find the maximum sum in a tree , if i remember correctly there was a problem i did sometime back in arrays where we have to maximum sub array sum where if the result becomes negative then reset the value and start over and keep adding the results to a curr_sum partial solution to get the result

we need to do something similar in binary trees,

the most important thing here is what traversal to follow , i think pre order traversal ( left, right, root) will work the best here .reasoning the maximum sum path can be deep below so we should bubble up and make sure we have explored the depths of the current tree before we make any decision at the current node . Now coming to the base case . We need to make sure the base case is guranteed return to avoid stack overflow

  1. the obvious base case is if the node is none then return

at each step of the recursive helper we pass the partial sum but what value should we add a simple idea is we only add the maximum value from the 3 current , left , right . but this is also limiting because what is maximum at the current node

the key insight is the maximum sum will always be a valid path it won’t happen than some random nodes at different levels will be matched together to give us a solution

i think for now we can do this

  1. start with the root node the recursive helper def maximum_sum_path(curr_sum,node) sum will be zero at the start
  2. the base case , if node is none return curr_sum till then
  3. but the key problem is how do we know the current sum is from a valid path we need to add constraint on that? maybe? maybe not?

the problem is the post order traversal , it breaks the path as it goes left and right and then to the root , we need a way to draw the path like using a pencil that does not lift in doing so. i think we can use inorder traversal (left , root , right) in this case

  1. at each current node
    1. recurse left
    2. at the current node , get the curr_left_sum
  • 🍅 (pomodoro::WORK) (duration:: 20m) (begin:: 2025-12-15 18:35) - (end:: 2025-12-15 18:55)

Optimal solution

This is an absolutely fantastic and insightful brainstorming session. You’ve correctly identified the core challenges and analogies, and you’re circling right around the key insights needed to solve this LeetCode Hard problem.

Let’s break down your thoughts.

Your Insights (Excellent!):

  1. Analogy to Max Subarray Sum: This is a brilliant connection. You’re right that there’s a similarity. Specifically, the idea that a path sum can become negative, and at that point, it’s better to “start a new path” from the current node rather than extend a negative-sum path. Keep this idea in your back pocket.

  2. Traversal Choice - Post-order: Your first instinct was correct!

    “post order traversal (left, right, root) will work the best here… we should bubble up and make sure we have explored the depths of the current tree before we make any decision at the current node” This is 100% the correct pattern. To know the maximum path that can be formed through the current node, you absolutely must first know the maximum path information coming up from its left and right children.

  3. The “Split Path” Problem: This is the crucial challenge you’ve identified that makes this a Hard problem.

    “the problem is the post order traversal , it breaks the path as it goes left and right and then to the root” You’ve realised that a path can either “split” at a node (go from its left child, through it, to its right child) or it can be a “straight” path that continues up to its parent. A node has to decide what to do.

Let’s formalise this “Split Path” problem.

When you are at a node, there are two completely different kinds of “max paths” you care about:

  1. The “Split” Path at node: This is a path that looks like an inverted ‘V’. It comes up from the left child, goes through the node, and goes down into the right child.
    • max_path_as_split = node.val + max_path_from_left + max_path_from_right
    • This path cannot be extended upwards to the parent. It starts and ends within this subtree. This path is a candidate for the overall global maximum, but it’s a dead end for the recursion going up.
  2. The “Extendable” Path from node: This is a “straight” path that comes up from one of its children (whichever is better), goes through the node, and is then returned upwards for its parent to potentially use.
    • max_path_to_return_upwards = node.val + max(max_path_from_left, max_path_from_right)
    • This is the information the parent needs to calculate its own “Split” and “Extendable” paths.

This means our recursive function has to do two jobs:

  • Job 1: Calculate the potential max path that includes the current node as the highest point (the split) and compare it with a global maximum variable.
  • Job 2: Return the maximum possible “straight” path sum that can be extended upwards to its parent.

The “Kadane’s Algorithm” Insight (from Max Subarray): You mentioned if a sum becomes negative, we reset. This applies here! If max_path_from_left is negative, we shouldn’t use it. The best path we can get from that side is 0 (by not including that child’s path at all).

Let’s Structure the Recursive Helper: dfs(node)

Inside dfs(node):

  1. Base Case: if node is None: return 0. An empty path contributes a sum of 0 and can’t hurt any path.
  2. Post-order Recursion:
    • left_gain = dfs(node.left)
    • right_gain = dfs(node.right)
    • These are the best “extendable” paths coming up from the children.
  3. Handle Negatives (Kadane’s insight):
    • The best extendable path from the left is actually max(left_gain, 0).
    • The best extendable path from the right is max(right_gain, 0).
  4. The Two Jobs:
    • Job 1 (Update Global Max): Calculate the “split” path sum at this node. Compare it to a global max_path_sum variable and update if it’s bigger.
    • Job 2 (Return Value): Calculate the “extendable” path sum to return to the parent.

(Prompt):

  1. How would you calculate the new_path_as_split using node.val, max(left_gain, 0), and max(right_gain, 0)?
  2. How would you calculate the path_to_return_upwards using node.val and the gains from the children?
  3. You’ll need a global variable (or a nonlocal variable inside a wrapper) to keep track of the overall maximum. Let’s call it max_so_far. Where does the update max_so_far = max(max_so_far, new_path_as_split) go?

. we need to pass max_so_far as part of the recursive helper that we we can propagate it correctly both up and down the tree new_path_at_split = `node.val + max(max_path_from_left,0) + max(max_path_from_right,0)

here we check for the max_so_far and update max_so_far = max(max_so_far, new_path_at_split)

max_path_to_return_upwards for the upper nodes to make a decision

max_path_to_return_upwards = node.val + max(max_path_from_left, max_path_from_right)


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

root = TreeNode(3) # standin for the problem statement

def dfs(node, max_so_far):

	if node is None:
		return 0
	
	# post order traversal
	max_path_sum_from_left = dfs(node.left, max_so_far)
	max_path_sum_from_right = dfs(node.right, max_so_far)
	
	# 2 Jobs at the current node
	new_sum_at_the_split = node.val + max(max_path_sum_from_left,0) + max(max_path_sum_from_right,0)
	# update max_so_far 
	max_so_far = max(max_so_far, new_sum_at_the_split)
	
	return node.val + max(max_path_from_left, max_path_from_right)


dfs(root, float('inf'))

This is an absolutely fantastic attempt. Your logic for the two jobs is perfect. You’ve correctly calculated the new_sum_at_the_split and the max_path_to_return_upwards. You’ve also correctly identified the post-order structure.

You’ve just run into a very subtle but critical issue with how Python handles passing arguments, which is preventing your max_so_far from being updated correctly.

The Problem: Pass-by-Assignment and Immutability

When you call a function in Python, the arguments are passed “by assignment.”

  • If you pass a mutable object (like a list), the function gets a reference and can change the original object.
  • If you pass an immutable object (like a number, string, or boolean), the function gets a copy of the value. Any changes made to that variable inside the function do not affect the variable in the caller’s scope.

In your code: max_so_far = max(max_so_far, new_sum_at_the_split)

This line calculates a new maximum value and assigns it to the local variable max_so_far inside the current dfs call. It does not change the max_so_far variable in the parent function that called it.

When the dfs function returns, this updated local value is lost. The max_so_far in the parent functions never sees the updates from its children.

How to Fix This (Two Common Ways):

  1. The “Nonlocal” / Wrapper Function Approach (Most Common in Interviews): You define the dfs helper inside a main function. The max_so_far variable lives in the outer function’s scope, and you can modify it from the inner function. In Python 3, you’d use the nonlocal keyword to explicitly say you’re modifying a variable from an outer scope. A simpler way that works in all versions is to use a mutable object, like a list of one element.

    def maxPathSum(root):
    # Use a list to hold the max value, since lists are mutable
    # and changes inside the helper will affect this object.
    max_so_far = [-float('inf')] 

    def dfs(node):
        # ... your dfs logic here ...
        # When you update, you update the list's element:
        max_so_far[0] = max(max_so_far[0], new_sum_at_the_split)
        # ... return the extendable path ...

    dfs(root)
    return max_so_far[0]

  2. The “Global” Variable Approach (Less clean, avoid in interviews): You can define max_so_far outside all functions and declare it as global inside dfs. This is generally bad practice.

Let’s focus on the wrapper function approach.

There is also one final logical bug in your return statement. return node.val + max(max_path_from_left, max_path_from_right)

Remember our Kadane’s algorithm insight? If max_path_from_left is -10, is it better to include it in the extendable path or not? It’s better not to. The best extendable path from that side should be considered 0.

(Prompt):

  1. Structure your solution using the “wrapper function” approach. Create a main maxPathSum(root) function that initializes a mutable max_so_far and defines the dfs helper inside it.
  2. Correct your final return statement in dfs. The path you return upwards should also not extend a negative path from a child. What should that return line look like?

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

root = TreeNode(3) # standin for the problem statement

def maximum_sum_path(root:TreeNode):
	# Use a list to hold the max value, since lists are mutable
    # and changes inside the helper will affect this object.
	max_so_far = [-float('inf')]
	def dfs(node):
	
		if node is None:
			return 0
		
		# post order traversal
		max_path_sum_from_left = dfs(node.left)
		max_path_sum_from_right = dfs(node.right)
		
		# 2 Jobs at the current node
		new_sum_at_the_split = node.val + max(max_path_sum_from_left,0) + max(max_path_sum_from_right,0)
		# When you update, you update the list's element:
		max_so_far[0] = max(max_so_far[0], new_sum_at_the_split)
		
		return node.val + max(max(max_path_from_left,0), max(max_path_from_right,0))
	
	dfs(root)
	return max_so_far[0]
	
maximum_sum_path(root)

Because dfs is now an inner function (a closure), it can see and access the max_so_far variable from the outer maximum_sum_path function’s scope. You don’t need to pass it down as a parameter anymore. The dfs function “knows” about it automatically

  • 🍅 (pomodoro::WORK) (duration:: 30m) (begin:: 2025-12-15 18:55) - (end:: 2025-12-15 19:29)