Skip to main content
Talentd

Binary Tree Maximum Path Sum - Solution & Explanation

HardDynamic ProgrammingTreeDepth-First SearchBinary Tree20 min readAsked at: Amazon, Microsoft, Apple +22
Practice this problem

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.

 

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.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 3 * 104].
  • -1000 <= Node.val <= 1000

Approach Overview

Problem Overview: You are given a binary tree where each node contains an integer (positive or negative). A path can start and end at any node, but it must follow parent-child connections. The task is to compute the maximum possible sum of values along any such path.

Approach 1: Recursive Depth-First Search (O(n) time, O(h) space)

This approach performs a postorder traversal using depth-first search. For every node, compute the maximum gain it can contribute to a path that extends upward to its parent. The key insight: a path passing through a node may include both left and right children, but a parent can only continue one side. During recursion, calculate left_gain = max(dfs(left), 0) and right_gain = max(dfs(right), 0). The candidate maximum path through the node becomes node.val + left_gain + right_gain, which updates a global maximum. The recursive function returns node.val + max(left_gain, right_gain) so the parent continues the best single branch. Every node is visited once, giving O(n) time. The recursion stack uses O(h) space where h is tree height.

Approach 2: Dynamic Programming with Tree Traversal (O(n) time, O(h) space)

This approach frames the same idea explicitly as dynamic programming on trees. Each node stores the best downward path sum starting from that node. While traversing the tree (typically postorder), compute two values: the best downward path returned to the parent and the best path passing through the node that may include both children. The recurrence relation is similar: downward = node.val + max(0, left, right). Meanwhile, update a global maximum with node.val + max(0,left) + max(0,right). The DP perspective emphasizes that each node's result depends only on its children’s computed values. Since each node contributes constant work and the traversal touches every node once, the runtime remains O(n) with O(h) auxiliary stack space.

Recommended for interviews: Interviewers typically expect the recursive DFS solution. It shows that you recognize a tree path can branch through a node but only one branch continues upward. Explaining the difference between the "global path" and the "extendable path" demonstrates strong understanding of tree recursion and dynamic programming on trees.

Approach 1: Recursive Depth-First Search Approach

This approach uses a recursive depth-first search (DFS) to explore every path in the binary tree. We calculate the maximum path sum that a node can contribute to its parent, which is the largest possible sum of the path from this node to any leaf node passing through this node. We keep updating the global maximum path sum during the recursion.

We define a nested function dfs that takes a node as an input and returns the maximum sum of the path that includes the node as an endpoint. The function recursively calculates the maximum path sum of the left and right subtrees. It then calculates the maximum path sum that includes the current node. We maintain a global variable dfs.max_sum to keep track of the maximum path sum encountered so far. Finally, the function returns the maximum path sum starting at the current node. We initialize the maximum path sum to negative infinity to ensure any path replaces it.

Code

PythonC++JavaScript

Python

C++

JavaScript

Complexity

Time Complexity: O(n), where n is the number of nodes in the binary tree. We traverse each node exactly once.
Space Complexity: O(h), where h is the height of the tree. This space is used by the call stack for recursion.

Try this approach in the editor →

Approach 2: Dynamic Programming with Tree Traversal Approach

In this approach, we utilize dynamic programming principles alongside tree traversal to compute the maximum path sum. This method is more about reformulating the tree's recursive structure into a form that allows storing intermediate results to optimize operations across the different subtrees. This method is especially useful for understanding different formulations but often overlaps logically with recursive DFS.

In this solution, we employ a recursive method calculateMaxSum that computes sub-results by leveraging already seen sub-tree sub-results. By traversing each node once, we update a global max value maxSum with results derived from each node acting as a center of a new path. This method hence avoids recomputation by relying on previously calculated results, drawing dynamic programming parallels.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(n), covering a single pass over all nodes.
Space Complexity: O(h), necessitated by call stack usage designated by the tree height h.

Try this approach in the editor →

Approach 3: Recursion

When thinking about the classic routine of recursion problems in binary trees, we consider:

  1. Termination condition (when to terminate recursion)
  2. Recursively process the left and right subtrees
  3. Merge the calculation results of the left and right subtrees

For this problem, we design a function dfs(root), which returns the maximum path sum of the binary tree with root as the root node.

The execution logic of the function dfs(root) is as follows:

If root does not exist, then dfs(root) returns 0;

Otherwise, we recursively calculate the maximum path sum of the left and right subtrees of root, denoted as left and right. If left is less than 0, then we set it to 0, similarly, if right is less than 0, then we set it to 0.

Then, we update the answer with root.val + left + right. Finally, the function returns root.val + max(left, right).

In the main function, we call dfs(root) to get the maximum path sum of each node, and the maximum value among them is the answer.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Depth-First Search Approach

Time Complexity: O(n), where n is the number of nodes in the binary tree. We traverse each node exactly once.
Space Complexity: O(h), where h is the height of the tree. This space is used by the call stack for recursion.

Dynamic Programming with Tree Traversal Approach

Time Complexity: O(n), covering a single pass over all nodes.
Space Complexity: O(h), necessitated by call stack usage designated by the tree height h.

Recursion—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Depth-First SearchO(n)O(h)Standard interview solution. Clean recursion with global maximum tracking.
Dynamic Programming with Tree TraversalO(n)O(h)When explaining the problem as DP on trees or implementing structured tree DP.

Video Solution

Binary Tree Maximum Path Sum - DFS - Leetcode 124 - Python • NeetCode • 247,569 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Binary Tree Maximum Path Sum easy or hard?
Binary Tree Maximum Path Sum is classified as a Hard problem because it requires understanding two different path concepts: the extendable path returned to the parent and the complete path passing through a node. Handling negative values and combining subtree results correctly makes it challenging.
Binary Tree Maximum Path Sum Python/Java solution
Python and Java implementations both use recursive DFS. The helper function returns the maximum gain from the current node while updating a global maximum path sum. Both implementations run in O(n) time and require O(h) stack space.
How to solve Binary Tree Maximum Path Sum in O(n)?
Perform a postorder DFS traversal and compute the maximum gain from each node. For each node, calculate left_gain and right_gain, ignoring negative contributions by clamping them to zero. Update a global maximum with node.val + left_gain + right_gain, and return node.val + max(left_gain, right_gain) to the parent.
What is the best approach for Binary Tree Maximum Path Sum?
The optimal approach uses depth-first search with dynamic programming on the tree. During a postorder traversal, compute the maximum gain from each child and update a global maximum path sum at every node. This solution processes each node once, giving O(n) time complexity and O(h) recursion stack space.
Is Binary Tree Maximum Path Sum asked at Google/Amazon/Meta?
Binary Tree Maximum Path Sum is a well-known hard tree problem frequently reported in interviews at companies like Google, Amazon, Meta, and Microsoft. It tests depth-first search, recursion, and the ability to reason about paths in trees with negative values.
What data structure is used in Binary Tree Maximum Path Sum?
The problem operates on a binary tree data structure. The solution typically uses recursion with depth-first search and maintains a global variable to track the maximum path sum while traversing the tree.
What is the time complexity of Binary Tree Maximum Path Sum?
The time complexity is O(n) where n is the number of nodes in the binary tree. Each node is visited exactly once during the DFS traversal. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

Ready to solve this problem?

Practice Binary Tree Maximum Path Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Difference Between Maximum and Minimum Price Sum

Next

Longest Univalue Path