Maximum Root-to-Leaf and Leaf-to-Leaf Path Sums
Updated
Problem statement
You are given the root of a binary tree. A leaf is a node with no children. The sum of a path is the sum of the values of all nodes on it, including both ends.
- A root-to-leaf path starts at the root and moves down, one child at a time, until it reaches a leaf.
- A leaf-to-leaf path connects two different leaves. It goes up from one leaf to a common ancestor and then down to the other leaf, and it visits no node twice. It does not have to pass through the root.
Return an array answer of length 2, where answer[0] is the largest sum of a root-to-leaf path and answer[1] is the largest sum of a leaf-to-leaf path.
A node with one child is not a leaf, so it can never be an end of a path, even when it is the root.
Function
maxPathSums(root: TreeNode) → int[]Examples
Example 1
root = [-5,8,12,null,null,6,4]return = [13,22]- The leaves are
8,6and4. The root-to-leaf sums are-5 + 8 = 3,-5 + 12 + 6 = 13and-5 + 12 + 4 = 11, so the first answer is13. - The leaf-to-leaf sums are
8 + (-5) + 12 + 6 = 21,8 + (-5) + 12 + 4 = 19and6 + 12 + 4 = 22. The best one does not pass through the root, and the second answer is22.
Example 2
root = [9,-3,null,4,5]return = [11,6]- The root has only one child, so it is not a leaf. The only leaves are
4and5. - The root-to-leaf sums are
9 + (-3) + 4 = 10and9 + (-3) + 5 = 11, so the first answer is11. - The only leaf-to-leaf path is
4 -> -3 -> 5, with sum6.
Example 3
root = [-1,-2,-3,-4,null,null,-5]return = [-7,-15]- Every value is negative, but a path must still end at leaves, so no node can be skipped.
- The root-to-leaf sums are
-1 + (-2) + (-4) = -7and-1 + (-3) + (-5) = -9, so the first answer is-7. - The only leaf-to-leaf path is
-4 -> -2 -> -1 -> -3 -> -5, with sum-15.
Constraints
- The number of nodes in the tree is in the range
[3, 104]. -1000 <= Node.val <= 1000- The tree has at least two leaves.
- The height of the tree, the number of nodes on its longest root-to-leaf path, is at most
500.
More Amazon Onsite Interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Optimal Account BalancingONSITE INTERVIEW · Seen Nov 2026
- Task SchedulerOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Number of IslandsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Binary Tree Level Order TraversalGoogle · ONSITE INTERVIEWGoogle interview questions
- Lowest Common Ancestor Only When Both Targets ExistAdobe · ONSITE INTERVIEWAdobe interview questions
- Sum Root-to-Leaf NumbersMeta · ONSITE INTERVIEWMeta interview questions
- Validate Binary Search TreeGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Balanced Tree Node ReportNetflix · ONSITE INTERVIEWNetflix interview questions
- Trim a Binary Search TreeBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Height-Balanced Binary TreeExpedia · ONSITE INTERVIEWExpedia interview questions
- Binary Tree Target-Sum PathsByteDance · PHONE SCREENByteDance interview questions
- Validate Binary Search TreeLyft · PHONE SCREENLyft interview questions
- Maximum Value in a Binary TreeAkuna Capital · PHONE SCREENAkuna Capital interview questions