LeetCode - Sum Root to Leaf Numbers

Problem statement

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

• For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Problem statement taken from: https://leetcode.com/problems/sum-root-to-leaf-numbers

Example 1:

Input: root = [1, 2, 3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: root = [4, 9, 0, 5, 1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Constraints:

- The number of nodes in the tree is in the range [1, 1000].
- 0 <= Node.val <= 9
- The depth of the tree will not exceed 10.

Explanation

Preorder Traversal

The idea is to use preorder traversal. We keep track of the value calculated till the current node. If the node is the leaf node we return the number generated. We traverse through all the tree paths from the root to the leaves and update the sum.

Let's check the algorithm to understand it clearly.

- if root == null
  - return 0

- sum = sum * 10 + root->val

// if leaf node return the number
- if root->left == NULL && root->right == NULL
  - return sum

// if a non-leaf node, compute the number of its leaf
- return sumNumbersHelper(root->left, sum) +
    sumNumbersHelper(root->right, sum)

The time complexity and the space complexity of the above approach is O(n).

Let's check our algorithm in C++, Golang, and JavaScript.

C++ solution

class Solution {
public:
    int sumNumbersHelper(TreeNode* root, int sum) {
        if(root == NULL) {
            return 0;
        }

        sum = sum * 10 + root->val;

        if(root->left == NULL && root->right == NULL) {
            return sum;
        }

        return sumNumbersHelper(root->left, sum) +
            sumNumbersHelper(root->right, sum);
    }

    int sumNumbers(TreeNode* root) {
        return sumNumbersHelper(root, 0);
    }
};

Golang solution

func sumNumbersHelper(root *TreeNode, sum int) int {
    if root == nil {
        return 0
    }

    sum = sum * 10 + root.Val

    if root.Left == nil && root.Right == nil {
        return sum
    }

    return sumNumbersHelper(root.Left, sum) +
        sumNumbersHelper(root.Right, sum)
}

func sumNumbers(root *TreeNode) int {
    return sumNumbersHelper(root, 0)
}

JavaScript solution

var sumNumbersHelper = function(root, sum) {
    if(root == null) {
        return 0;
    }

    sum = sum * 10 + root.val;

    if(root.left == null && root.right == null) {
        return sum;
    }

    return sumNumbersHelper(root.left, sum) +
        sumNumbersHelper(root.right, sum);
}

var sumNumbers = function(root) {
    return sumNumbersHelper(root, 0)
};

Dry Run

Let's dry-run our algorithm to see how the solution works.

Input: root = [1, 2, 3]

// sumNumbers
Step 1: return sumNumbersHelper(root, 0)

// sumNumbersHelper
Step 2: if root == NULL
          root -> 1
          false

Step 3: sum = sum * 10 + root->val
            = 0 * 10 + 1
            = 1

Step 4: root->left == NULL && root->right == NULL
        root -> 1
        root->left = 2
        root->right = 3

        false

Step 5: return sumNumbersHelper(root->left, sum) +
            sumNumbersHelper(root->right, sum)

        return sumNumbersHelper(2, 1) +
            sumNumbersHelper(3, 1)

// We call the function sumNumbersHelper(2, 1)
Step 6: if root == NULL
          root -> 2
          false

Step 7: sum = sum * 10 + root->val
            = 1 * 10 + 2
            = 12

Step 8: root->left == NULL && root->right == NULL
        root -> 2
        root->left = NULL
        root->right = NULL

        true

        return sum

// We backtrack to Step 5
Step 9: return sumNumbersHelper(root->left, sum) +
            sumNumbersHelper(root->right, sum)

        return sumNumbersHelper(2, 1) +
            sumNumbersHelper(3, 1)

        return 12 + sumNumbersHelper(3, 1)

// We call the function sumNumbersHelper(3, 1)
Step 10: if root == NULL
          root -> 3
          false

Step 11: sum = sum * 10 + root->val
            = 1 * 10 + 3
            = 13

Step 12: root->left == NULL && root->right == NULL
        root -> 3
        root->left = NULL
        root->right = NULL

        true

        return sum

// We backtrack to Step 9
Step 13: return 12 + sumNumbersHelper(3, 1)
         return 12 + 13
         return 25

// We reach the main function Step 1
Step 14: return 25