Brute Force Approach
In this method, we begin by tracing all of the routes from root-to-leaf. Following that, we transform all pathways into numbers. We'll add those numbers at the end of the solution. We will then return the added amount.
Algorithm
1. Begin tracing every route from the root node to the leaf node by doing a simple depth-first search of the input tree.
2. Transform the node values in the path into strings and and store them in a vector of strings currentPath. This vector will hold all the strings encountered in a route from the root node to the leaf node.
3. When you reach a leaf node, store currentPath in another array namely everyPath.
4. Finally, traverse the everyPath array and for each of its elements (which are themselves vector of strings) do the following:
-
Add up all the strings in each of its vector of strings and convert the final string into an integer namely k.
-
Maintain a global value sum adding up the value of k after each iteration.
5. Print the added value.
Implementation
#include <bits/stdc++.h>
using namespace std;
// Defining the Binary tree node
class Node
{
public:
int val;
Node *left, *right;
};
Node *createNode(int val)
{
Node *newNode = new Node();
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
void pathSum(Node *head, vector<string> currentPath,
vector<vector<string>> &everyPath)
{
// Base Case
if (head == NULL)
return;
currentPath.push_back((to_string)(head->val));
if (head->left == NULL && head->right == NULL)
everyPath.push_back(currentPath);
// traverse in the left subtree
pathSum(head->left, currentPath, everyPath);
// traverse in the right subtree
pathSum(head->right, currentPath, everyPath);
currentPath.pop_back();
}
int treePathsSum(Node *head)
{
// store every root-to-leaf path in vector of vector
vector<vector<string>> everyPath;
vector<string> currentPath;
pathSum(head, currentPath, everyPath);
// store the sum
int sum = 0;
for (int i = 0; i < everyPath.size(); i++)
{
vector<string> path = everyPath[i];
string k = "";
// join the pathNumbers to convert them
// into the number to calculate sum
for (int j = 0; j < path.size(); j++)
{
k = k + path[j];
}
sum += stoi(k);
}
return sum;
}
// Driver code
int main()
{
Node *head = createNode(6);
head->left = createNode(3);
head->right = createNode(5);
head->left->left = createNode(2);
head->left->right = createNode(5);
head->right->right = createNode(4);
head->left->right->left = createNode(7);
head->left->right->right = createNode(4);
cout << "The Sum of all paths is " << treePathsSum(head);
return 0;
}
You can also try this code with Online C++ Compiler
Output
The Sum of all paths is 13997
Time Complexity
Since we are traversing everyPath array and joining currentPath to the everyPath array, the time complexity of this technique will be O(n^2). Here n refers to the count of nodes in the binary tree.
Space Complexity
The Space complexity of the above approach is O(n), as a vector is used for storing all the numbers formed in root-to-leaf paths. Here n refers to the count of nodes in the binary tree.
Optimized Approach
The solution approach for the given problem is quite an interesting one. The intention is to traverse the tree in preorder. Keep track of the value computed until the current node in the preorder traversal, and let this value be val. We will update the val as val*10 plus the node's data for each node.
Algorithm
1. Start a preorder traversal of the given binary tree.
2. We will now keep track of the value calculated till now in the preorder traversal.
3. Store this value in a variable, e.g., val.
4. As we go through each node, we update this val by multiplying it by 10 plus the node’s data for each number.
5. Print out the sum of all these formed values of val.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
// Defining the Binary tree node
class Node
{
public:
int val;
Node *left, *right;
};
Node *createNode(int val)
{
Node *newNode = new Node();
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int pathSum(Node *head, int val)
{
// Base case
if (head == NULL)
return 0;
// Update val
val = (val * 10 + head->val);
if (head->left == NULL && head->right == NULL)
return val;
// recur sum of values for both of the left and right subtree
return pathSum(head->left, val) +
pathSum(head->right, val);
}
// A wrapper function over pathSum()
int treePathsSum(Node *head)
{
// Pass the initial value as 0
// as there is nothing above root
return pathSum(head, 0);
}
// Driver code
int main()
{
Node *head = createNode(6);
head->left = createNode(3);
head->right = createNode(5);
head->left->left = createNode(2);
head->left->right = createNode(5);
head->right->right = createNode(4);
head->left->right->left = createNode(7);
head->left->right->right = createNode(4);
cout << "The Sum of all paths is " << treePathsSum(head);
return 0;
}
You can also try this code with Online C++ Compiler
Output
The Sum of all paths is 13997
Time Complexity
The above code is a straightforward preorder traversal code that visits each precisely once. The time complexity is, therefore, O(n), where n is the count of nodes in the specified binary tree.
Space Complexity
Due to the recursion call stack, the Space complexity of the above approach is O(n). Here n refers to the count of nodes in the binary tree.
Check out this problem - Root To Leaf Path
Frequently Asked Questions
What is a Trie?
Trie is a data structure that stores a set of strings as a sorted tree. Each node has the same number of pointers as the number of alphabet characters.
What is the file bits/stdc++.h?
The header bits/stdc++.h includes all standard libraries. This is useful when you don't want to waste time including many header files.
What are the uses of a Pre-order traversal?
Preorder traversal is used to duplicate the tree. Preorder traversal is also utilized on an expression tree to obtain the prefix expression.
Conclusion
In this blog, we discussed a coding problem in which we calculated the sum of all the numbers formed while traversing the root-to-leaf paths of a given binary tree. We discussed two approaches: First approach was a brute force approach where we traversed all routes from the root node to the leaf nodes and added up their values. Second approach employed a pre-order tricky solution to get the answer in O(N) time complexity.
Cheers, you have reached the end. Hope you liked the blog and it has added some knowledge to your life. Please look at these similar topics to learn more: Binary Tree, Binary Search Tree, Binary Tree to BST, and All Binary Trees.
Refer to our Coding Ninjas Studio Guided Path to learn Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and even more! You can also check out the mock test series and participate in the contests hosted by Coding Ninjas Studio! But say you're just starting and want to learn about questions posed by tech titans like Amazon, Microsoft, Uber, and so on. In such a case, for placement preparations, you can also look at the problems, interview experiences, and interview bundle.
You should also consider our premium courses to offer your career advantage over others!
Please upvote our blogs if you find them useful and exciting!
Happy Coding!
24+ registered 
