Problem 124

Abstract / Summary

Find the highest total value from any path between nodes in a binary tree.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0124.py

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        @cache
        def deeper(node, limit): # limit = max. direct child nodes
            if not node:
                return 0

            if not node.left and not node.right:
                self.best = max(self.best, node.val)
                return node.val

            l1 = deeper(node.left,  1)
            r1 = deeper(node.right, 1)
            l2 = deeper(node.left,  2)
            r2 = deeper(node.right, 2)
            me = node.val
            if limit == 1:
                result = max(me, me + l1, me + r1)
            else: # limit == 2
                result = max(me, me + l1, me + r1, me + l1 + r1)

            self.best = max(self.best, result)
            return result

        self.best = root.val
        deeper(root, 2)
        return self.best
27 lines | 879 bytes | submitted August 30, 2023 | GitHub   8% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 43% (4+ million submissions).

Typical patterns to solve this problem:
  • Binary Tree
  • Depth First Search
  • Dynamic Programming
  • Tree
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a class Solution with a method maxPathSum that computes the maximum sum obtainable by any path in a binary tree. A path is defined as a sequence of nodes where each consecutive pair is connected by a parent-child edge, and the path may start and end at any nodes in the tree. The algorithm uses a depth-first traversal combined with memoization to explore possible contributions from each subtree while maintaining a global best value.

Key Steps

The entry point maxPathSum initializes a mutable attribute self.best with the value of the root node and then invokes the nested helper function deeper on the root with a limit of 2.

self.best = root.val
deeper(root, 2)
return self.best

The helper deeper is decorated with @cache, which automatically stores the result of each call keyed by the node reference and the limit argument. This memoization prevents repeated evaluation of identical subproblems during the recursive exploration.

@cache
def deeper(node, limit):
    ...

Inside deeper, the first guard checks for a null node and returns 0. This base case ensures that leaf-level recursion terminates cleanly without contributing to the path sum.

if not node:
    return 0

When a node is a leaf (both children are None), the algorithm updates the global best with the leaf’s value and returns that value as the maximum sum that can be extended upward from this leaf.

if not node.left and not node.right:
    self.best = max(self.best, node.val)
    return node.val

For internal nodes, the function recursively obtains four values: the best single-child contributions when the limit is 1 (l1 and r1) and the best contributions when the limit is 2 (l2 and r2). The limit parameter controls whether the current node may combine contributions from both children (limit == 2) or only a single child (limit == 1).

l1 = deeper(node.left,  1)
r1 = deeper(node.right, 1)
l2 = deeper(node.left,  2)
r2 = deeper(node.right, 2)

The variable me holds the node’s own value. The result for the current call is computed by considering different combinations based on the limit. When the limit is 1, the result is the maximum of the node alone, the node plus the left contribution, and the node plus the right contribution. When the limit is 2, the result also includes the possibility of adding both left and right contributions together with the node’s value.

me = node.val
if limit == 1:
    result = max(me, me + l1, me + r1)
else:  # limit == 2
    result = max(me, me + l1, me + r1, me + l1 + r1)

After computing result, the global best is updated to reflect any larger path sum discovered at this node. The function then returns result, which represents the maximum sum that can be propagated upward to the node’s parent under the current limit constraint.

self.best = max(self.best, result)
return result

Edge Cases Handled

The algorithm explicitly handles the situation where the input tree consists of a single node. In that case, the leaf-node guard updates self.best with the node’s value and the recursion terminates, yielding the correct maximum path sum.

When a subtree is missing (i.e., a child reference is None), the early return of 0 ensures that absent branches do not contribute to the path sum, effectively treating them as neutral elements in the max calculations.

The limit parameter distinguishes between paths that may extend through both children versus those that must continue through only one child. This distinction allows the function to correctly evaluate paths that terminate at the current node versus those that pass through it, covering scenarios where the optimal path either bends at the node or proceeds linearly upward.

Performance Optimizations

Memoization via the @cache decorator is the primary optimization. By caching the results of deeper for each (node, limit) pair, the algorithm avoids recomputing the same subtree contributions multiple times, which is especially beneficial in trees with overlapping substructures or when the same node is visited under different limit contexts.

The use of a single mutable attribute self.best eliminates the need to propagate intermediate best values up the call stack, reducing the amount of data passed between recursive frames. Updating self.best immediately after each node’s computation ensures that the global optimum is always available without additional traversal.

Limiting the recursive calls to only the necessary combinations (limit == 1 and limit == 2) prevents unnecessary exploration of paths that would violate the problem’s constraints, thereby focusing computational effort on relevant scenarios.

Overall, the combination of memoization, in-place global tracking, and constrained recursion yields an efficient solution that scales well with the size of the input tree.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a beautiful tree made of treasure chests instead of branches. Each chest has a number written on the lid, which represents how many gold coins are hiding inside it. The goal is to find the longest path through the tree that grabs the most gold possible.

The code starts at the very top of the tree, which is called the root. It sends out tiny explorers to peek into every single path. These explorers move down to the left and to the right, looking at the chests they find along the way.

There are two ways the explorers handle their collection. Sometimes, they are only allowed to follow one path down from a chest, and other times they are allowed to look at both the left and right sides together to make a bigger path. Every time an explorer finishes looking at a path, they check the total number of gold coins they found. They keep track of the highest number they have seen so far in a special box called best.

The explorers keep diving deeper and deeper into the tree until they reach the chests at the very tips of the branches. By the time they have visited every path, the special box will hold the biggest score discovered during the adventure.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 4 | μ = 4.30 | σ = 1.96

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python C# Java Rust JS Go TS
LeetcodeHelp C++ Python Java
MemoryLimitExceeded C++ Python
Progiez C++ Python Java
github aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows C++
charles-wangkai Java
chenyanzhe C++
everthis JS
FelixFan1122 C#
fengvyi C++
fpdjsns C++
gaosq0604 Python
Garvit244 Python
gouthampradhan Java
halfrost Go
haoel C++
JoshCrozier JS
keineahnung2345 C++
linouk23 C++
lkwq007 Python
luangong C++
MacJim C++
qiyuangong Python
ruoru Rust
shreymehul C#
sonugiri1043 C++
suxrobGM C#
varunu28 Java
vli02 C
wisdompeak C++
XiaotaoGuo C++
yuanliu666 Kotlin
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp C++, Java, Python
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
chenyanzhe C++
everthis JavaScript
FelixFan1122 C#
fengvyi C++
fpdjsns C++
gaosq0604 Python
Garvit244 Python
gouthampradhan Java
halfrost Go
haoel C++
JoshCrozier JavaScript
keineahnung2345 C++
linouk23 C++
lkwq007 Python
luangong C++
MacJim C++
qiyuangong Python
ruoru Rust
shreymehul C#
sonugiri1043 C++
suxrobGM C#
varunu28 Java
vli02 C
wisdompeak C++
XiaotaoGuo C++
yuanliu666 Kotlin
zfang399 C++
55 links | 38 authors | 10 languages

Videos

These are a few popular YouTube videos for this problem:
YouTube video 'Binary Tree Maximum Path Sum - DFS - Leetcode 124 - Python'
NeetCode 16 mins
Binary Tree Maximum Path Sum - DFS - Leetcode 124 - Python
YouTube video 'Binary tree maximum path sum | Leetcode #124'
Techdose 16 mins
Binary tree maximum path sum | Leetcode #124
YouTube video 'LeetCode 124. Binary Tree Maximum Path Sum (Algorithm Explained)'
Nick White 17 mins
LeetCode 124. Binary Tree Maximum Path Sum (Algorithm Explained)
YouTube video 'Binary Tree Maximum Path Sum | Leetcode - 124 | Trees - 10'
Algorithms Made Easy 9 mins
Binary Tree Maximum Path Sum | Leetcode - 124 | Trees - 10
YouTube video 'Dp on Trees Template | Binary Tree Maximum Path Sum | Leet Code 124 | Dp on Tree Basics'
Coding Decoded 21 mins
Dp on Trees Template | Binary Tree Maximum Path Sum | Leet Code 124 | Dp on Tree Basics
YouTube video 'Binary Tree Maximum Path Sum | (C++, Java, Python) | 30 day Challenge | Day 29 | LeetCode #124'
Knowledge Center 24 mins
Binary Tree Maximum Path Sum | (C++, Java, Python) | 30 day Challenge | Day 29 | LeetCode #124
YouTube video 'Binary Tree Maximum Path Sum | Leetcode 124 | Binary Tree'
Ayushi Sharma 15 mins
Binary Tree Maximum Path Sum | Leetcode 124 | Binary Tree
YouTube video '[Java] Leetcode 124. Binary Tree Maximum Path Sum [Binary Tree #16]'
Eric Programming 11 mins
[Java] Leetcode 124. Binary Tree Maximum Path Sum [Binary Tree #16]
YouTube video 'BINARY TREE MAX PATH SUM | PYTHON | LEETCODE 124'
Cracking FAANG 21 mins
BINARY TREE MAX PATH SUM | PYTHON | LEETCODE 124
YouTube video '124. Binary Tree Maximum Path Sum | Day 007 | Most Asked Question of Trees'
Aryan Mittal 16 mins
124. Binary Tree Maximum Path Sum | Day 007 | Most Asked Question of Trees
YouTube video 'Binary Tree Maximum Path Sum - LeetCode 124 - Python  #leetcode #binarytree #blind75 #recursion'
Deepti Talesra 13 mins
Binary Tree Maximum Path Sum - LeetCode 124 - Python #leetcode #binarytree #blind75 #recursion
YouTube video 'LeetCode 124. Binary Tree Maximum Path Sum [Coding Interview Solution Explained]'
Shiran Afergan 19 mins
LeetCode 124. Binary Tree Maximum Path Sum [Coding Interview Solution Explained]
YouTube video 'LeetCode 124. Binary Tree Maximum Path Sum [Coding Interview Solution Explained]'
Shiran Afergan 19 mins
LeetCode 124. Binary Tree Maximum Path Sum [Coding Interview Solution Explained]
YouTube video '[Animated] LeetCode 124 Binary Tree Maximum Path Sum | Blind 75'
Code In Motion 16 mins
[Animated] LeetCode 124 Binary Tree Maximum Path Sum | Blind 75
YouTube video 'Binary Tree Maximum Path Sum - LeetCode 124 - JavaScript'
AlgoJS 8 mins
Binary Tree Maximum Path Sum - LeetCode 124 - JavaScript
YouTube video 'LeetCode 124. Binary Tree Maximum Path Sum Explanation and Solution'
happygirlzt 6 mins
LeetCode 124. Binary Tree Maximum Path Sum Explanation and Solution
YouTube video 'LeetCode 124. Binary Tree Maximum Path Sum 中文解释 Chinese Version'
happygirlzt 6 mins
LeetCode 124. Binary Tree Maximum Path Sum 中文解释 Chinese Version
YouTube video 'Daily Leetcode #985: Dec 11, 2022 - 124. Binary Tree Maximum Path Sum'
Programming Live with Larry 7 mins
Daily Leetcode #985: Dec 11, 2022 - 124. Binary Tree Maximum Path Sum
YouTube video 'Leetcode 124: Binary Tree Maximum Path Sum in Telugu | Recursive DFS | Python DSA | srkcodes'
Srk Codes 9 mins
Leetcode 124: Binary Tree Maximum Path Sum in Telugu | Recursive DFS | Python DSA | srkcodes
YouTube video 'Microsoft Coding Interview Question | Leetcode 124 | Binary Tree Maximum Path Sum'
WorkWithGoogler 17 mins
Microsoft Coding Interview Question | Leetcode 124 | Binary Tree Maximum Path Sum
20 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

7 similar problems

Solved On The Same Day

1 easy 3 medium 1 hard
6 solutions   August 30, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality