Get Sum of all nodes formed from Root to Leaf Path

Question:

Given a binary tree root node, get the sum of the values of all the nodes formed from root to the leaf node.

Solution:

From the above image, we have 4 leaf nodes i.e : 3, 4, 6, 7

So the paths will be

1 -> 2 -> 3 Number = 123
1 -> 2 -> 4 Number = 124
1 -> 5 -> 6 Number = 156
1 -> 5 -> 7 Number = 157

So the sum will be:
123 + 124 + 156 + 157 = 560

Solution is to do pre order traversal and keep track of the value calculated till that node.

For every node multiply the value with 10 + node’s data.

Solution in C++

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};


int value_root_to_leaf;

void sum_root_to_leaf(Node *node, int i) 
{
    if (node == NULL) 
    {
      return;
    }

    if (node->left == NULL && node->right == NULL) 
    {
      value_root_to_leaf = value_root_to_leaf + (i * 10 + node->data);
      return;
    }

    sum_root_to_leaf(node->left, i * 10 + node->data);
    sum_root_to_leaf(node->right, i * 10 + node->data);
}



int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              1
            /   \
           /     \
          2       5
         /  \    /  \
        /    \  /    \
       3     4 6      7

    */

    root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(5);
    root->left->left = new Node(3);
    root->left->right = new Node(4);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    sum_root_to_leaf(root, 0);

    cout<<"The sum of root to leaf is "<<value_root_to_leaf<<endl;

    return 0;  
}  

Output

The sum of root to leaf is 560