Sum numbers formed by root-to-leaf paths
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given the root of a binary tree where each node contains a single digit from 0 to 9.
Each root-to-leaf path represents a number obtained by concatenating the digits along the path from the root down to a leaf. For example, if a path is root → 1 → 2 → 3, it represents the number 123.
Write a function that returns the sum of all numbers formed by all root-to-leaf paths in the tree.
- Input: the root node of a binary tree.
- Output: an integer representing the sum of all root-to-leaf numbers.
Constraints:
- Each node value is a digit from 0 to 9.
- The tree has at most 1000 nodes.
Describe your algorithm and its time and space complexity. You do not need to provide actual code.
Quick Answer: This question evaluates a candidate's ability to work with binary tree traversal and path-based numerical aggregation, testing competency in tree data structures and algorithmic reasoning within the Coding & Algorithms domain.
Given a binary tree in level-order form, sum the numbers represented by each root-to-leaf digit path.
Constraints
- Each node value is a digit 0..9; None represents a missing node
Examples
Input: ([1, 2, 3],)
Expected Output: 25
Explanation: 12 + 13.
Input: ([4, 9, 0, 5, 1],)
Expected Output: 1026
Explanation: 495 + 491 + 40.
Input: ([],)
Expected Output: 0
Explanation: Empty tree.
Input: ([0, 1],)
Expected Output: 1
Explanation: Leading zero path.
Hints
- Carry the current prefix value during DFS.