Tree Binary Tree Binary Search Tree Breadth First Search Depth First Search
Intermediate Level

Implement the sumRootToLeafNumbers method that returns the sum of all root-to-leaf numbers in a binary tree.

You are given binary tree values in level-order array form, where 0 represents a missing node. Every root-to-leaf path forms a number by joining the node digits along that path.

Return the sum of all numbers formed by root-to-leaf paths. For example, a path 1 -> 2 -> 3 forms the number 123.

Example 1
Input:
tree (int[]) = [1,2,3]
size (int) = 3
Return:
(int) 25
Example 2
Input:
tree (int[]) = [4,9,8,5,1]
size (int) = 5
Return:
(int) 1034
Example 3
Input:
tree (int[]) = [1]
size (int) = 1
Return:
(int) 1

Use depth-first search and carry the number formed so far.

When visiting a node, update the current value as current * 10 + node value. If the node is a leaf, add this value to the answer. Otherwise, continue to the left and right children.

This builds each path number without storing the full path.

Pseudocode:

function sumRootToLeafNumbers(tree, size):
    function dfs(index, current):
        if index is invalid or tree[index] is 0:
            return 0
        current = current * 10 + tree[index]
        if node at index is a leaf:
            return current
        return dfs(left child index, current) + dfs(right child index, current)
    return dfs(0, 0)
Run your code to see the result.