Binary Tree Maximum Path Sum
On this page
Problem statement
Given the root of a binary tree, return the largest sum of any path in it. A path is a chain of nodes where each pair of neighbors is joined by an edge, and no node appears twice. It must contain at least one node, it can start and end anywhere, and it does not have to pass through the root. Node values can be negative.
This is the classic "hard" tree question, and it shows up often because the fix for the obvious mistake is one line that many candidates can't explain. Original problem: LeetCode 124.
Example

Input: root = [-10, 9, 20, null, null, 15, 7]
Output: 42 # 15 + 20 + 7
Input: root = [-3]
Output: -3 # all values negative: the answer is the largest single node
Constraints (assumed)
- 1 ≤ number of nodes ≤ 30,000.
- −1,000 ≤ node value ≤ 1,000.
What this question tests
- Splitting one hard quantity (best path anywhere) into a simple quantity you can return up (best one-sided path) plus a global answer you update on the way.
- Handling negative values: when to drop a branch, and why the answer can still be negative.
- Explaining clearly why the value you return differs from the value you record.
Questions to ask first
- Can values be negative? (Yes. This is the whole difficulty.)
- Must the path include the root, or end at a leaf? (Neither.)
- Can the path be a single node? (Yes, it needs at least one node.)
- How deep can the tree be? A very deep, skewed tree may need an iterative DFS to avoid a stack overflow.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.