Binary Tree Maximum Path Sum
Updated
Problem statement
You are given the root of a binary tree. Every node holds an integer, and it may be negative.
A path is a chain of nodes in which each node is joined to the next by a parent-child link, and no node appears twice. A path has at least one node. It may start and end at any nodes, so it does not have to include the root or end at a leaf. The sum of a path is the total of the values of its nodes.
Return the largest sum of any path.
Function
maxPathSum(root: TreeNode) → intExamples
Example 1
root = [-5,7,-2,3,-1]return = 10The best path is 3 -> 7, with sum 10. It turns at node 7 and does not use the root.
The other child of node 7, which is -1, would lower the sum, so the path skips it. The path through the root, 3 -> 7 -> -5, has sum 5, and the single node 7 has sum 7. No path beats 10.
Example 2
root = [-8]return = -8The tree has one node, and a path needs at least one node. The only path is [-8], so the answer is -8.
Example 3
root = [2,-1,8,null,null,-3,6]return = 16The best path is 2 -> 8 -> 6, with sum 16. It passes through the root, goes down the right side to node 6, and skips the negative node -1 and the negative node -3.
Other paths are smaller: 8 -> 6 is 14, and -1 -> 2 -> 8 -> 6 is 15.
Example 4
root = [1,-2,3,4,5,-6,2]return = 9The best path is 5 -> -2 -> 1 -> 3 -> 2, with sum 9. It goes up from node 5 through the negative node -2 to the root 1, then down through node 3 to node 2.
Crossing -2 is worth it: it costs 2 and brings in the 5 behind it. The other candidates are 4 -> -2 -> 1 -> 3 -> 2 with 8 and 1 -> 3 -> 2 with 6.
Constraints
- The tree has between
1and500nodes. -1000 <= node.val <= 1000
More Bloomberg LP Onsite Interview questions
- N-ary Index-Path Encoder and DecoderPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Top K Frequent WordsONSITE INTERVIEW · Seen Nov 2026
- Trapping Rain WaterPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Word SearchOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Design Browser HistoryPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Mutable Stock Price Top KPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Add Two Numbers IIPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Decode StringPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Minimum Replacements to Make Two Strings AnagramsPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Currency Conversion RatePHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
Similar questions at other companies
- Sum of Weighted Distances in a TreeGoogle · ONSITE INTERVIEWGoogle interview questions
- File Encryption Tree OptimizationDatabricks · PHONE SCREEN · ONSITE INTERVIEWDatabricks interview questions
- Binary Tree Maximum Path SumGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Binary Tree Maximum Path SumGlobalization Partners · ONSITE INTERVIEW
- Transitive Employee Referral CountsRobinhood · ONSITE INTERVIEWRobinhood interview questions
- Maximum Nonadjacent Sum in a General TreeZip · PHONE SCREEN · ONSITE INTERVIEWZip interview questions
- Maximum Sum of Non-Adjacent Tree NodesInMobi · ONSITE INTERVIEWInMobi interview questions
- Distance Sums to Special Nodes in a Weighted TreeNutanix · ONSITE INTERVIEWNutanix interview questions
- Minimum Leaf Path Sum over All RootsInfosys · OAInfosys interview questions
- Part 2: Batch Access ReviewScale AI · OAScale AI interview questions
Bloomberg LP interview experiences
- Bloomberg SWE Phone Screen and Onsite: 1 Experience
- Bloomberg SWE Phone Screens with Two Teams: 1 Experience
- Bloomberg AI Interview, Hiring Level Not Reported: 2 Experiences
- Bloomberg Experienced SWE AI Coding Interviews: 2 Experiences
- Bloomberg New Grad AI-Assisted Coding Rounds: 3 Experiences
- Bloomberg New Grad SWE AI-Assisted Coding Rounds: 1 Experience