Sum Rootto Leaf Numbers Algorithm
The Sum Root to Leaf Numbers Algorithm is a tree traversal technique used to find the sum of all the numbers formed by the paths from the root node to the leaf nodes in a given binary tree. In this algorithm, each node in the tree represents a digit, and the number is formed by concatenating the digits along the path from the root to the leaf. The algorithm involves a depth-first search approach, which explores each path from the root to the leaf and calculates the sum of the numbers formed along the way. The final result is the sum of all the numbers found in each path.
To implement this algorithm, a recursive function is used to traverse the binary tree. The function starts at the root node, and at each step, the current digit is concatenated to the number formed so far. The function is then called recursively for the left and right children of the current node. When a leaf node is reached, the number formed so far is added to a running total. Once all paths have been explored, and the recursive function has returned to the root node, the final sum of all the numbers formed from the root to the leaf nodes is returned. This algorithm is efficient in solving problems that require the calculation of the sum of all root-to-leaf numbers in a binary tree, such as those encountered in coding interviews and competitive programming contests.
/**
*
* Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
*
* An example is the root-to-leaf path 1->2->3 which represents the number 123.
*
* Find the total sum of all root-to-leaf numbers.
*
* For example,
*
* 1
* / \
* 2 3
* The root-to-leaf path 1->2 represents the number 12.
* The root-to-leaf path 1->3 represents the number 13.
*
* Return the sum = 12 + 13 = 25.
*/
#include <iostream>
#include <vector>
struct TreeNode {
int val;
TreeNode * left;
TreeNode * right;
TreeNode( int data ) : val{ data }, left{ nullptr }, right{ nullptr } { }
};
void rootToLeafSum( TreeNode* root, int & total, int & curr ) {
if( root == nullptr ) {
return;
}
curr = (10*curr) + root->val;
if (root && root->left == nullptr && root->right == nullptr ) {
total += curr;
}
int oldCurr = curr;
rootToLeafSum(root->left, total, curr);
rootToLeafSum(root->right, total, oldCurr);
}
int sumNumbers(TreeNode* root) {
int total = 0;
int curr = 0;
rootToLeafSum(root, total, curr);
return total;
}
void printTree( TreeNode * root ) {
if ( root ) {
printTree( root->left );
std::cout << root->val << " ";
printTree( root->right );
}
}
int main() {
TreeNode * root = new TreeNode( 1 );
root->left = new TreeNode( 2 );
root->right = new TreeNode( 3 );
std::cout << "Tree in order:";
printTree(root);
std::cout << "Output : " << sumNumbers(root) << std::endl;
return 0;
}
