Given a binary tree, where each node has a value between 0 and 9, find the total sum of all root-to-leaf numbers. A root-to-leaf number is a number represented by the concatenation of all node values along the path from the root to that leaf.
Table of Contents
Sample Input:
Tree:
1
/ \
2 3
Expected Output:
25
In this example, there are two root-to-leaf numbers: 12 and 13. The sum of these two numbers is 25.
Time and Space Complexity:
The time complexity of the algorithm is O(n), where ‘n’ is the number of nodes in the binary tree. We need to visit each node once to compute the sum. The space complexity is O(h), where ‘h’ is the height of the binary tree. In the worst case, the recursion stack can grow to the height of the tree.
C++ solution:
#include <iostream>
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int sumNumbers(TreeNode* root, int currentSum) {
// Base case: if the root is null, the sum for this path is 0
if (root == nullptr) {
return 0;
}
// Calculate the sum for this path, considering the current node value
currentSum = currentSum * 10 + root->val;
// If it's a leaf node, return the sum for this path
if (root->left == nullptr && root->right == nullptr) {
return currentSum;
}
// Recursively calculate the sum for left and right subtrees
int leftSum = sumNumbers(root->left, currentSum);
int rightSum = sumNumbers(root->right, currentSum);
// Return the total sum for this path
return leftSum + rightSum;
}
int sumNumbers(TreeNode* root) {
return sumNumbers(root, 0);
}
int main() {
// Construct the binary tree for the sample input
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
// Find the total sum of all root-to-leaf numbers
int totalSum = sumNumbers(root);
std::cout << "The total sum of all root-to-leaf numbers is: " << totalSum << std::endl;
// Don't forget to free the allocated memory
// ...
return 0;
}
The sumNumbers function recursively calculates the total sum of all root-to-leaf numbers in the binary tree. It starts from the root node and calculates the sum for each path using the current sum (which is the concatenation of node values along the path from the root). When it reaches a leaf node, it returns the sum for that path.
In the given example, the function will correctly find the total sum of all root-to-leaf numbers as 25, and the output will be 25.
As mentioned earlier, the time complexity is O(n) as we need to visit each node once, and the space complexity is O(h) due to the recursion stack, where ‘h’ is the height of the binary tree.