Sum of all the numbers that are formed from root to leaf paths

Hello Everyone,

Given a binary tree, where every node value is a Digit from 1-9 .Find the sum of all the numbers which are formed from root to leaf paths.

For example consider the following Binary Tree.

The idea is to do a preorder traversal of the tree. In the preorder traversal, keep track of the value calculated till the current node, let this value be val . For every node, we update the val as val10* plus node’s data.

// C++ program to find sum of

// all paths from root to leaves

#include <bits/stdc++.h>

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(6);

root->left = newNode(3);

root->right = newNode(5);

root->left->left = newNode(2);

root->left->right = newNode(5);

root->right->right = newNode(4);

root->left->right->left = newNode(7);

root->left->right->right = newNode(4);

cout<< "Sum of all paths is " <<treePathsSum(root);

return 0;

}

Output:

Sum of all paths is 13997

Time Complexity: The above code is a simple preorder traversal code which visits every exactly once. Therefore, the time complexity is O(n) where n is the number of nodes in the given binary tree.