[DFS] Binary Tree Maximum Path Sum

[sudosf]

Problem

Given a binary tree, find the maximum path sum. A path is any sequence of nodes where each pair of adjacent nodes has an edge. The path does not need to pass through the root.

References

• LeetCode: https://leetcode.com/problems/binary-tree-maximum-path-sum/
• GFG: https://www.geeksforgeeks.org/problems/maximum-path-sum-from-any-node/1
• Sheet: https://www.risingbrain.org/sheet#tree (DFS Traversals [Sliding Window] Subarray Product Less Than K #14)
• Parent: Pattern: DFS (Trees + Graphs) #30

Difficulty

🔴 Hard

Companies

Microsoft, Facebook, Morgan Stanley

Notes

Language: Java
Track global max separately. Each recursive call returns max gain from that node going downward (not the split path).