Return all root-to-leaf path sums
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem
You are given the root of a **binary tree** where each node contains an integer value (may be negative).
Return an array/list containing the **sum of values along every path from the root to a leaf** (a leaf is a node with no children).
## Input
- `root`: root node of a binary tree.
## Output
- A list of integers, where each integer is the sum of one root-to-leaf path.
- The order of sums can be any consistent traversal order (e.g., DFS order).
## Examples
1) Tree:
```
5
/ \
4 8
/ \
11 4
```
Root-to-leaf sums are:
- 5→4 = 9
- 5→8→11 = 24
- 5→8→4 = 17
Output (one valid): `[9, 24, 17]`
2) Single node `-3` → output `[-3]`
## Constraints (typical interview assumptions)
- Number of nodes: up to ~10^4
- Node values fit in 32-bit signed integer
## Notes
- If the tree is empty, return an empty list.
Overview: This question evaluates competency in binary tree traversal and path-state accumulation, focusing on the ability to compute sums along root-to-leaf paths while handling edge cases like empty trees and negative values.
Read the full Meta Software Engineer interview experience this question came from
Trees are [value,left,right]. Return root-to-leaf sums in DFS left-to-right order.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([5,[4,None,None],[8,[11,None,None],[4,None,None]]],)
Expected Output: [9, 24, 17]
Explanation: DFS root-to-leaf sums.
Input: ([-3,None,None],)
Expected Output: [-3]
Explanation: Single node path.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.