Katkat
Back

Compute root-to-leaf number sum

ByteDanceSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to perform depth-first search on a binary tree and maintain state (the current path sum) during the traversal to compute a cumulative total.

Problem Statement

You are given the root of a binary tree where each node contains a single-digit integer value from 0 to 9. Each root-to-leaf path represents a number. For example, if the path is 1 -> 2 -> 3, it represents the number 123.

Calculate the sum of all numbers represented by every root-to-leaf path in the tree. A leaf node is a node with no children.

Function Signature

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sumNumbers(root: TreeNode) -> int:
    pass

Examples

Example 1: Input: root = [1, 2, 3] Path 1-2: 12 Path 1-3: 13 Output: 25 (12 + 13)

Example 2: Input: root = [4, 9, 0, 5, 1] Path 4-9-5: 495 Path 4-9-1: 491 Path 4-0: 40 Output: 1026 (495 + 491 + 40)

Constraints

  • The number of nodes in the tree is in the range [1, 1000].
  • Each node's value is between 0 and 9.
  • The depth of the tree will not exceed 10.

Hints

Hint 1

Consider a recursive helper function that takes the current node and the current number formed by its ancestors as arguments.

Hint 2

When moving from a parent to a child, the new path value is calculated as (current_path_value * 10) + child_node_value.

Hint 3

When you reach a leaf node, return the accumulated path value; if it's an internal node, sum the results from its left and right subtrees.

Follow-up questions

  • How would you modify your solution if each node could contain a multi-digit number instead of just a single digit?
  • Could you solve this problem using an iterative approach, such as Breadth-First Search (BFS) or an explicit stack?
  • What is the space complexity of your solution, and can you optimize it to O(h) where h is the tree height?