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.