Maximum Root-to-Leaf Path Sum
Updated
Problem statement
Given a binary tree root, return the maximum sum of node values along a path that begins at the root and ends at an actual leaf. A leaf has no children.
For this exercise, return the sum, rather than the sequence of nodes. Every node on the chosen path contributes its value, including the root and leaf. Values may be negative: you must still reach a leaf and cannot stop at an internal node or skip a negative child. For an empty tree, return 0. A nonempty tree can also have maximum sum zero.
Function
maxRootToLeafSum(root: TreeNode) → intExamples
Example 1
root = [5,4,8,11,null,13,4,7,2,null,null,null,1]return = 27The leaf paths have sums 27 for 5→4→11→7, 22 for 5→4→11→2, 26 for 5→8→13, and 18 for 5→8→4→1. The maximum is 27.
Example 2
root = [-5,null,-7]return = -12The root has only the right child -7. The only root-to-leaf path is -5→-7, whose sum is -12. Stopping at the root would not reach a leaf.
Constraints
- For this exercise, assume the tree has between 0 and 500 nodes.
- For this exercise, assume -1000000 <= node values <= 1000000.
- The input is a valid finite binary tree.
More Morgan Stanley Onsite Interview questions
- Generate Strings of Length at Least ThreeONSITE INTERVIEW · Seen Sep 2026
- Maximum Concurrent ProcessesOA · ONSITE INTERVIEW · Seen Sep 2026
- Kth Largest Array ElementONSITE INTERVIEW · Seen Jul 2026
- Run-Length Encode Consecutive Letter RunsONSITE INTERVIEW · Seen Jul 2026
- Maximum Edge Removals for Two TravelersONSITE INTERVIEW · Seen Oct 2025
- Remove K DigitsONSITE INTERVIEW · Seen Oct 2025
- Count Ideal ArraysONSITE INTERVIEW · Seen Aug 2023
- Distinct Palindrome PartitionsONSITE INTERVIEW · Seen Aug 2023
- LFU Cache OperationsONSITE INTERVIEW · Seen Aug 2023
- All-Pairs Shortest PathsOA · ONSITE INTERVIEW · Seen Feb 2022
Similar questions at other companies
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEW
- Delete Nodes and Return Forest RootsGoogle · ONSITE INTERVIEW
- Render a Task Tree from CSV RowsStripe · PHONE SCREEN · ONSITE INTERVIEW
- Filter Undesired Comments and Their DescendantsReddit · PHONE SCREEN · ONSITE INTERVIEW
- JSON Path Lookup with Implicit Array WildcardsMongoDB · ONSITE INTERVIEW
- Maximum Sum Among Longest Root-to-Leaf PathsAmazon · ONSITE INTERVIEW
- Delete and Compact a Forest SubtreePinterest · PHONE SCREEN · ONSITE INTERVIEW
- Onion-Peel Layers of a Binary TreeeBay · ONSITE INTERVIEW
- Match a Descendant Selector in a DOM TreeMicrosoft · ONSITE INTERVIEW
- Serialize and Deserialize an N-Ary TreeUber · ONSITE INTERVIEW