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.