Binary Tree Maximum Path Sum
Reported by candidates from Arcesium's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The input cap on this Arcesium OA, reported in August 2023, is 3 * 10^4 non-missing nodes. That kills any approach that tries every pair of nodes and sums the path between them. This is Binary Tree Maximum Path Sum with a twist: the tree arrives as a level-order array with -1001 marking missing children, so you build it first, then solve it. It's a tree DFS problem with one clean trick. If you know it, it's 20 minutes. If you blank, StealthCoder runs invisibly during the live OA as your safety net.
The problem
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.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Build the tree from the array with a queue. Pop a node, take the next two array values as its children, skip any equal to -1001, and enqueue the real ones. Then run a post-order DFS. At each node, compute the best downward gain from the left and right children, and clamp each at zero, because a negative branch is better dropped. The best path bending through this node is value + left + right, so update a global max with that. Return value + max(left, right) to the parent, since a parent can only extend one side. The classic pitfall is returning the bent path upward, which reuses a node twice. The other one is initializing the global max to 0, which breaks on all-negative trees like [-3]. Start at negative infinity. Recursion depth can hit 3 * 10^4 on a skewed tree, so consider an iterative post-order. StealthCoder is the hedge if the recursion setup slips under pressure.
StealthCoder is the hedge for the one pattern you didn't drill. It runs invisibly during the screen share.
You can drill Binary Tree Maximum Path Sum cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. If you're reading this with an OA window open, you're who this was built for.
Get StealthCoderRelated leaked OAs
This OA pattern shows up on LeetCode as binary tree maximum path sum. If you have time before the OA, drill that.
You've seen the question.
Make sure you actually pass Arcesium's OA.
Arcesium reuses patterns across OAs. If you're reading this with an OA window open, you're who this was built for. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Binary Tree Maximum Path Sum FAQ
What's the trick to Binary Tree Maximum Path Sum?+
Post-order DFS where each node returns its best one-sided downward gain, while a global variable tracks the best bent path through that node. Clamp child gains at zero so negative branches get ignored. The answer is the global max, not the root's return value.
How do I decode the -1001 level-order array?+
Use a queue. Create the root from index 0. For each popped node, read the next two entries as left and right children. If an entry is -1001, leave that child empty. Otherwise create a node and enqueue it. Missing children don't consume further slots.
Why does an all-negative tree break some solutions?+
Initializing the global max to 0 returns 0 for a tree like [-3], but the path must be non-empty, so the answer is -3. Initialize to negative infinity, and only clamp child contributions at zero, never the node's own value.
Will recursion overflow with 3 * 10^4 nodes?+
It can on a fully skewed tree, depending on your language's stack limit. Either raise the recursion limit or write an iterative post-order using an explicit stack and a map of computed gains. Know which one you'd pick before the assessment starts.
How do I prepare for this in 48 hours?+
Write the tree builder once from memory, then write the DFS once from memory. Test on the three examples, including the single negative node. Those two pieces are the whole problem. Practice the clamp-at-zero and return-one-side logic until it's automatic.