Katkat
Back

Return all root-to-leaf path sums

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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]
  1. 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.