Root to leaf paths sum

Given a binary tree, where every node value is a number. Find the sum of all the numbers that are formed from root to leaf paths. The formation of the numbers would be like 10*parent + current (see the examples for more clarification).

Examples:

Input :      

Output: 13997
Explanation : There are 4 leaves, resulting in leaf path of 632, 6357, 6354, 654 sums to 13997.

Input :    

Output : 2630
Explanation: There are 3 leaves, resulting in leaf path of 1240, 1260, 130 sums to 2630.

Input :    
           1
          /
         2                    
Output : 12
Explanation: There is 1 leaf, resulting in leaf path of 12.

Constraints:
1 ≤ number of nodes ≤ 31
1 ≤ node->data ≤ 100

Approach 01:

#include <vector>
using namespace std;

class Solution {
public:
    void calculatePathSums(Node* root, vector<int>& pathSums, int currentSum) {
        currentSum = currentSum * 10 + root->data;
        if (!root->left && !root->right) {  // If it's a leaf node
            pathSums.push_back(currentSum);
            return;
        }
        if (root->left) {
            calculatePathSums(root->left, pathSums, currentSum);
        }
        if (root->right) {
            calculatePathSums(root->right, pathSums, currentSum);
        }
    }

    int treePathsSum(Node* root) {
        vector<int> pathSums;
        calculatePathSums(root, pathSums, 0);
        int totalSum = 0;
        for (int pathSum : pathSums) {
            totalSum += pathSum;
        }
        return totalSum;
    }
};

class Solution:
    def calculatePathSums(self, root, pathSums, currentSum):
        currentSum = currentSum * 10 + root.data
        if not root.left and not root.right:  # If it's a leaf node
            pathSums.append(currentSum)
            return
        if root.left:
            self.calculatePathSums(root.left, pathSums, currentSum)
        if root.right:
            self.calculatePathSums(root.right, pathSums, currentSum)

    def treePathSum(self, root) -> int:
        pathSums = []
        self.calculatePathSums(root, pathSums, 0)
        totalSum = sum(pathSums)
        return totalSum

Time Complexity

• Tree Traversal:

  The function traverses each node in the binary tree exactly once to calculate all root-to-leaf path sums. Since there are \( N \) nodes in the tree, the time complexity is \( O(N) \).

• Path Sum Computation:

  The `calculatePathSums` function accumulates the sum as it traverses the path, performing constant-time operations at each node. Thus, no additional complexity is added.

• Overall Time Complexity:

  The overall time complexity is \( O(N) \).

Space Complexity

• Recursive Call Stack:

  The depth of the recursive calls depends on the height of the tree, which in the worst case can be \( O(N) \) for a skewed tree, and \( O(\log N) \) for a balanced tree. Thus, the recursive call stack uses \( O(H) \) space, where \( H \) is the tree height.

• Path Sum Storage:

  The `pathSums` vector stores an integer for each leaf node’s path sum. In the worst case, there can be \( O(N) \) leaf nodes, so the space complexity for storing path sums is \( O(N) \).

• Overall Space Complexity:

  The overall space complexity is \( O(N) \), considering both the recursive stack and the path sums storage.