HardDynamic ProgrammingTreeDepth-First SearchBinary TreeUpdated Sep 2026

124. Binary Tree Maximum Path Sum

Asked at Amazon, Adobe, Salesforce, Goldman Sachs

Difficulty

Hard

Time

O(n)

Space

O(h)

Pattern

Dynamic Programming

Companies

4

Problem

You are given the root of a binary tree. A path is a chain of nodes where each node is connected to the next by an edge. You may move up or down, but each node can appear at most once in a path. The path does not have to start or end at the root.

The path sum is the total of all node values on that path. Your job is to return the largest path sum over all possible paths. The path must contain at least one node, so an empty path is not allowed.

Because node values can be negative, the best answer may be a single node. Do not assume you should always include more nodes.

A path can bend at one node

212 + 1 + 3 = 63The path goes up from 2 to 1, then down to 3.
The path 2 → 1 → 3 uses both children of the root and has sum 6, which is the best answer.

Constraints

  • ●The number of nodes is in the range [1, 3 * 10^4].
  • ●-1000 <= Node.val <= 1000

Examples

Example 1
Inputroot = [1,2,3]
Output6
WhyThe best path goes 2 → 1 → 3. It uses the left child, the root, and the right child, giving 2 + 1 + 3 = 6. Any single node or one-sided path is smaller.
Example 2
Inputroot = [-10,9,20,null,null,15,7]
Output42
WhyThe best path is 15 → 20 → 7. It stays inside the right subtree and avoids the negative root, giving 15 + 20 + 7 = 42.

Asked At

4 companies
CompanyDifficulty
AmazonHardView all Amazon questions →
AdobeHardView all Adobe questions →
SalesforceHardView all Salesforce questions →
Goldman SachsHardView all Goldman Sachs questions →

How to Think About It

1

Brute force: for every pair of nodes, find the path between them and compute the sum. This is O(n^2) for a tree. Too slow.

2

Key insight: at each node, the maximum path either (a) passes through this node (connecting left and right subtrees) or (b) stays within one subtree. Use DFS to compute the maximum "arm" (single-branch path) from each node, and use a global variable to track the maximum path sum overall.

3

DFS returns the maximum arm sum: the maximum sum of a path starting at this node and going down to one of its children. At each node: compute left_arm = max(0, dfs(left)) and right_arm = max(0, dfs(right)). The path through this node is left_arm + node.val + right_arm. Update the global max. Return node.val + max(left_arm, right_arm) (the arm extending upward).

4

Why max(0, child_arm): if the child's arm is negative, it is better to not include it (start the path at the current node). This handles trees with all negative values correctly.

5

Time: O(n) — visit each node once. Space: O(h) — recursion stack where h is the tree height.

Optimal Approach

Use DFS with a global variable max_sum.

dfs(node):

  1. If node is null, return 0.
  2. left = max(0, dfs(node.left)) — max arm from left (clamp negatives to 0).
  3. right = max(0, dfs(node.right)) — max arm from right.
  4. path_through_node = left + node.val + right. Update max_sum = max(max_sum, path_through_node).
  5. Return node.val + max(left, right) — the arm extending to parent.

Walkthrough: tree with root=-10, left=9, right=20 (left=15, right=7).

  • dfs(9): left=0, right=0. path=9. max=9. return 9.
  • dfs(15): path=15. max=15. return 15.
  • dfs(7): path=7. max=15. return 7.
  • dfs(20): left=15, right=7. path=20+15+7=42. max=42. return 20+15=35.
  • dfs(-10): left=max(0,9)=9, right=max(0,35)=35. path=-10+9+35=34. max=42.
    Result: 42.

Time: O(n). Space: O(h).

DFS returns one arm, tracks the bend

9-1015arm 152015+20+7=427arm 7Node 20 joins its two arms: 15 + 20 + 7 = 42, the bestpath.9arm 9-10−10+9+35=341520arm 357At the root, the bent path is only 34, so the answerstays 42.left = max(0, dfs(left))right = max(0, dfs(right))best = max(best, left + val + right)return val + max(left, right)
Each node reports its best single-side arm upward, while a global value keeps the best bent path seen so far.
ComplexityTime O(n)Space O(h)Every node is visited once, and the recursion stack holds at most one root-to-leaf chain, where h is the tree height.

What Trips People Up in Real Interviews

1

Forgetting to clamp child arm values to 0 with max(0, child_arm). If a subtree has a negative sum, including it would decrease the path sum. Clamping to 0 means "don't include this subtree." Without this, the algorithm fails on trees with negative values.

2

Confusing "path" with "path from root to leaf." A path can start and end at any node. The path through a node connects its left and right subtrees. This is different from root-to-leaf paths.

3

Returning left + node.val + right from DFS instead of node.val + max(left, right). The DFS must return the maximum arm (single branch) for the parent to use. Returning the full path through the node would double-count when the parent uses it.

4

Not using a global or class-level variable for max_sum. The recursive DFS cannot easily return both the arm sum and the global max. Use a class variable, a nonlocal variable (Python), or pass a mutable reference.

5

Handling single-node trees. If the tree has one node with a negative value, the answer is that negative value (the path is just that node). The algorithm handles this correctly because max_sum is initialized to negative infinity and the path through the single node is its value.

Solution Code

O(n) time
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):
        self.max_sum = float('-inf')

        def dfs(node):
            if not node:
                return 0
            left = max(0, dfs(node.left))
            right = max(0, dfs(node.right))
            self.max_sum = max(self.max_sum, left + node.val + right)
            return node.val + max(left, right)

        dfs(root)
        return self.max_sum

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Binary Tree Maximum Path Sum 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. The path sum is the sum of the node values. Given the root of a binary tree, return the maximum path sum of any non-empty path.

How do you solve Binary Tree Maximum Path Sum?

The optimal approach runs in O(n) time and O(h) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Binary Tree Maximum Path Sum?

Binary Tree Maximum Path Sum is asked at Amazon, Adobe, Salesforce, Goldman Sachs. It is a hard difficulty problem.

What are common mistakes on Binary Tree Maximum Path Sum?
  • Forgetting to clamp child arm values to 0 with `max(0, child_arm)`. If a subtree has a negative sum, including it would decrease the path sum. Clamping to 0 means "don't include this subtree." Without this, the algorithm fails on trees with negative values.
  • Confusing "path" with "path from root to leaf." A path can start and end at any node. The path through a node connects its left and right subtrees. This is different from root-to-leaf paths.
  • Returning `left + node.val + right` from DFS instead of `node.val + max(left, right)`. The DFS must return the maximum arm (single branch) for the parent to use. Returning the full path through the node would double-count when the parent uses it.
  • Not using a global or class-level variable for `max_sum`. The recursive DFS cannot easily return both the arm sum and the global max. Use a class variable, a nonlocal variable (Python), or pass a mutable reference.
  • Handling single-node trees. If the tree has one node with a negative value, the answer is that negative value (the path is just that node). The algorithm handles this correctly because `max_sum` is initialized to negative infinity and the path through the single node is its value.