How do you approach Binary Tree Maximum Path Sum?

Use DFS to compute the maximum path sum passing through each node.

What is the time complexity of Binary Tree Maximum Path Sum?

Time complexity: O(n). Space complexity: O(h) where h is the tree height.

What are common mistakes on Binary Tree Maximum Path Sum?

Handling the null node deep in the recursion instead of as the first base case. Returning early from a subtree when the answer needs both sides explored. Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

Sitelet https://gitgood.dev/coding/binary-tree-maximum-path-sum

gitGood.dev

← Back to problems

Binary Tree Maximum Path Sum

HardData Structures

Description

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.

Note: The tree is represented as an array in level-order (BFS) format, where null represents missing nodes.

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 * 10^4]. - -1000 <= Node.val <= 1000

Binary Tree Maximum Path Sum: approach, complexity and pitfalls

A hard trees problem, graded against 7 test cases (4 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

If you are stuck

Show the 3-step hint ladder

Use DFS to compute the maximum path sum passing through each node.
At each node, you can extend the path through the left child, right child, or both.
The value returned up should only include one side (left or right), not both.

The optimal approach

Show the approach: DFS with Global Maximum

For each node, compute the maximum gain from its left and right subtrees (clamped to 0 to ignore negative paths). The path through this node has sum = node.val + leftGain + rightGain. Track the global maximum. Return node.val + max(leftGain, rightGain) to the parent since a path can only go one direction.

Time: O(n)
Space: O(h) where h is the tree height

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Null values. A null appears in the input. Guard your dereferences rather than relying on the shape of the sample case.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.