One calculates the sum of all the numbers from the root to the leaf by creating each number separately. The method can be divided into the following steps:
The tree is traversed from the root node until the leaf node, and then a single number is created and stored.
Once a number is stored, another number is created, and then the traversal begins from the root node again.
This repeats until all the paths are traversed and all of the numbers are retrieved from the tree.
The total number of numbers retrieved is always equal to the number of leaf nodes.
The following implements the algorithm mentioned above:
#include <iostream> using namespace std; class node { public: int data; node *left, *right; }; // function to allocate new node with given data node* newNode(int data) { node* Node = new node(); Node->data = data; Node->left = Node->right = NULL; return (Node); } // Returns sum of all root to leaf paths. // The first parameter is root // of current subtree, the second // parameter is value of the number formed // by nodes from root to this node int treePathsSumUtil(node *root, int val) { // Base case if (root == NULL) return 0; // Update val val = (val*10 + root->data); // if current node is leaf, return the current value of val if (root->left==NULL && root->right==NULL) return val; // recur sum of values for left and right subtree return treePathsSumUtil(root->left, val) + treePathsSumUtil(root->right, val); } // A wrapper function over treePathsSumUtil() int treePathsSum(node *root) { // Pass the initial value as 0 // as there is nothing above root return treePathsSumUtil(root, 0); } // Driver code int main() { node *root = newNode(3); root->left = newNode(2); root->right = newNode(2); root->left->left = newNode(7); root->right->right = newNode(8); root->right->left = newNode(5); cout<<"Sum of all paths is "<<treePathsSum(root); return 0; }
RELATED TAGS
View all Courses