Binary Tree Maximum Path Sum

Hard · Trees

You are given the root of a binary tree where each node holds an integer value. A path is any sequence of nodes where each pair of adjacent nodes in the sequence is connected by an edge, and no node appears more than once in it; the path does not need to pass through the root. Return the largest possible sum of node values along any such path. Node values can be negative, so a path may consist of just a single node if extending it would only reduce the sum.

Examples

Input:  root = [1,2,3]
Output: 6
Why:    The best path goes 2 -> 1 -> 3, giving sum 2+1+3 = 6.

Input:  root = [-10,9,20,null,null,15,7]
Output: 42
Why:    The best path is 15 -> 20 -> 7, entirely within the right subtree, giving sum 15+20+7 = 42.

Input:  root = [-3]
Output: -3
Why:    There is only one node so the maximum path is that single node.

Constraints

1 <= number of nodes <= 3 * 10^4, -1000 <= Node.val <= 1000

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Binary Tree Maximum Path Sum

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Binary Tree Maximum Path Sum. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.