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