Related Tags

sum
numbers
from
root
leaf

How to sum all the numbers formed from root to leaf

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:

1. The tree is traversed from the root node until the leaf node, and then a single number is created and stored.

2. Once a number is stored, another number is created, and then the traversal begins from the root node again.

3. 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.

1 of 14

Code

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

sum
numbers
from
root
leaf