Sum root to leaf path

129.Sum Root to Leaf Numbers

Tree

Depth First Search

Recursion

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. Return the total sum of all root-to-leaf numbers.

Example:

Input:

root = [1,2,3]

→

Output:

25 (12 + 13)

Java Solution:

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

// Remember answer bubbles up so only add sum to return value with both 
// nodes are null
int recurse(TreeNode node, int sum) {
    if (node == null) return 0;

    sum = sum * 10 + node.val;  // Build number by multiplying by 10 and adding current digit
    
    if (node.right == null && node.left == null)  // Leaf node
        return sum;
    
    return recurse(node.left, sum) + recurse(node.right, sum);  // Sum both paths
}

Python Solution:

def sumNumbers(self, root: TreeNode) -> int:
    def recurse(node: TreeNode, curr_sum: int) -> int:
        if not node:
            return 0
            
        curr_sum = curr_sum * 10 + node.val
        
        if not node.left and not node.right:
            return curr_sum
            
        return recurse(node.left, curr_sum) + recurse(node.right, curr_sum)
    
    return recurse(root, 0)

C++ Solution:

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return recurse(root, 0);
    }
    
private:
    int recurse(TreeNode* node, int sum) {
        if(!node) return 0;
        
        sum = sum * 10 + node->val;
        
        if(!node->left && !node->right)
            return sum;
            
        return recurse(node->left, sum) + recurse(node->right, sum);
    }
};

Complexity:

Time: O(N) | Space: O(H) where H is tree height