Sum Root to Leaf Numbers - LeetCode Daily Challenge

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.

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.

Try here before watching the video.

Video Solution

Java Code

class Solution {

    private int solve(TreeNode root, int sum) {
        if(root == null) {
            return 0;
        }

        sum = sum * 10 + root.val;
        if(root.left == null && root.right == null) {
            return sum;
        }

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

    public int sumNumbers(TreeNode root) {
        return solve(root, 0);
    }
}

C++ Code

class Solution {
private:
    int solve(TreeNode* root, int sum) {
        if (root == nullptr) {
            return 0;
        }

        sum = sum * 10 + root->val;
        if (root->left == nullptr && root->right == nullptr) {
            return sum;
        }

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

public:
    int sumNumbers(TreeNode* root) {
        return solve(root, 0);
    }
};

Python Code

class Solution:
    def solve(self, root, sum):
        if root is None:
            return 0
        
        sum = sum * 10 + root.val
        if root.left is None and root.right is None:
            return sum
        
        return self.solve(root.left, sum) + self.solve(root.right, sum)
    
    def sumNumbers(self, root):
        return self.solve(root, 0)

Javascript Code

var sumNumbers = function(root) {
    const solve = (node, sum) => {
        if (!node) return 0;
        
        sum = sum * 10 + node.val;
        if (!node.left && !node.right) return sum;
        
        return solve(node.left, sum) + solve(node.right, sum);
    };
    
    return solve(root, 0);
};

Go Code

func solve(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 solve(root.Left, sum) + solve(root.Right, sum)
}

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

Complexity Analysis

Time Complexity: O(N), because we traverse all N nodes.
Space Complexity: O(N), because the tree might be skewed in the worst case and therefore the stack might occupy N space for storing recursive calls.