Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Sample Example 1
2.2.
Sample Example 2
3.
Brute Force Approach
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
Optimized Approach
4.1.
Algorithm
4.2.
Implementation in C++
4.2.1.
Time Complexity
4.2.2.
Space Complexity
5.
Frequently Asked Questions
5.1.
What is a Trie?
5.2.
What is the file bits/stdc++.h?
5.3.
What are the uses of a Pre-order traversal?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

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

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

This blog covers a problem related to the binary tree data structure. Binary Trees are among the most important and often asked data structures in programming contests and technical interviews. There are various standard Binary Tree problems and techniques. This blog tackles a coding task that involves calculating the sum of all the numbers that are formed from root-to-leaf paths of the given binary tree.

Problem Statement

Ninja has a coding duel with his friend, who gives him a binary tree where every node is given a value between 1 and 9. Ninja is challenged to find the sum of all the numbers which are formed from root-to-leaf paths. He has asked for your help in this task. Can you help Ninja to win this duel?

Sample Example 1

Input

Output

2895

Explanation

There are five root-to-leaf paths. Therefore there are five numbers formed on root-to-leaf routes, which are 1248,1249,125,136, and 137.

The sum of all these numbers comes out to be 2895.

Sample Example 2

Input

Output

2282

Explanation

There are five root-to-leaf paths. Therefore there are five numbers formed on root-to-leaf routes, which are 568,569,573, and 572.

The sum of all these numbers comes out to be 2282.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

 

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;
}


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 TreeBinary Search TreeBinary 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 problemsinterview 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!

Previous article
Find the sum of all right leaves in a given Binary Tree
Next article
Print all Prime Levels of a Binary Tree
Live masterclass