Binary Tree Maximum Path Sum
Updated
Problem statement
You are given a non-empty binary tree encoded by the integer array levelOrder.
The array lists nodes in breadth-first order. The value -1001 marks a missing child; every other value is a tree node. Children are consumed from left to right only for non-missing nodes.
A path is a sequence of nodes in which each adjacent pair is connected by an edge. A node may appear at most once, and the path does not need to pass through the root.
Return the maximum sum of node values along any non-empty path.
Function
maxPathSum(levelOrder: int[]) → intExamples
Example 1
levelOrder = [-10,9,20,-1001,-1001,15,7]return = 42The best path is 15 -> 20 -> 7, whose sum is 42.
Example 2
levelOrder = [1,2,3]return = 6The path 2 -> 1 -> 3 contains all three nodes and sums to 6.
Example 3
levelOrder = [-3]return = -3A path must be non-empty, so the single node gives the maximum sum -3.
Constraints
- The tree contains between
1and3 * 10^4non-missing nodes. - Every node value is in the range
[-1000, 1000]. levelOrder[0] != -1001.levelOrderis a valid compact breadth-first encoding, and-1001appears only as the missing-child marker.
More Arcesium Online Assessment questions
- City Infection NumberOA · Seen Jul 2025
- Minimum Tunnel Crossing TimeOA · Seen Jul 2025
- Product of Subset MaximaOA · Seen Jul 2025
- Reconstruct the Root StreamOA · Seen Jul 2025
- Add DigitsOA · Seen Aug 2023
- Detect a Cycle in Directed Hate RelationshipsOA · Seen Aug 2023
- Reverse First K Characters in Every 2K BlockOA · Seen Aug 2023
- Robo Data Sharing DirectionOA · Seen Jul 2023
- Capital Gains Tax from TradesOA · Seen Feb 2021
- K-th Character in an Infinite StringOA · Seen Aug 2020
Similar questions at other companies
- Minimum Leaf Path Sum over All RootsInfosys · OAInfosys interview questions
- Part 2: Batch Access ReviewScale AI · OAScale AI interview questions
- Binary Tree CamerasAmazon · OA · PHONE SCREEN
- Maximum Sum Path Between Two Leaf NodesGoogle · OAGoogle interview questions
- Maximum Strength of Every NeuronMicrosoft · OAMicrosoft interview questions
- Tree PointsThe D.E. Shaw Group · OAThe D.E. Shaw Group interview questions
- Tree Node With Maximum BeautyC3.ai · OAC3.ai interview questions
- Best Sum Downward Tree PathCitadel · OACitadel interview questions
- Longest Alternating a/b Path in a TreeHudson River Trading · OAHudson River Trading interview questions
- Maximum Reservoir PowerWells Fargo · OAWells Fargo interview questions