Sum of Digit Paths in a Tree

You are given a binary tree root with each node containing single digits from 0 to 9. Each path from the root to the leaf represents a number with its digits in order.

Return the sum of numbers represented by all paths in the tree.

https://binarysearch.com/problems/Sum-of-Digit-Paths-in-a-Tree

Examples

Example 1

Input

• root =

Output

• answer = 25

Explanation

We have 12 + 13 = 25.

Example 2

Input

• root =

Output

• answer = 680

Explanation

We have the following numbers represented by paths:

• 35 (3 → 5)
• 321 (3 → 2 → 1)
• 324 (3 → 2 → 4)

Solution