FastPrepBinary Tree Maximum Path Sum
Problems/Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

Arcesium logoArcesium● HardINTERNOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in an Arcesium intern online assessment. The report names the well-known Binary Tree Maximum Path Sum task. Our version is about 98% the same as the reported question.

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[]) → int

Examples

Example 1

levelOrder = [-10,9,20,-1001,-1001,15,7]return = 42

The best path is 15 -> 20 -> 7, whose sum is 42.

Example 2

levelOrder = [1,2,3]return = 6

The path 2 -> 1 -> 3 contains all three nodes and sums to 6.

Example 3

levelOrder = [-3]return = -3

A path must be non-empty, so the single node gives the maximum sum -3.

Constraints

  • The tree contains between 1 and 3 * 10^4 non-missing nodes.
  • Every node value is in the range [-1000, 1000].
  • levelOrder[0] != -1001.
  • levelOrder is a valid compact breadth-first encoding, and -1001 appears 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
All Arcesium interview questionsSee Arcesium hiring insights
Saved
class Solution {
    public int maxPathSum(int[] levelOrder) {
      // Write your code here.
    }
}
Checking account…