Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

sum
numbers
from
root
leaf

How to sum all the numbers formed from root to leaf

Educative Answers Team

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
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring