Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Example: 
1.1.1.
Input
1.1.2.
Output
1.2.
Explanation
2.
Intuition
3.
Approach
3.1.
Algorithm
3.2.
Program
3.3.
Output
3.4.
Time Complexity
3.5.
Space complexity
4.
Frequently Asked Questions
4.1.
What are some real-world applications of the Binary Tree data structure?
4.2.
What is the Red-Black tree data structure?
4.3.
How can you determine whether a binary tree is a subtree of another binary tree?
4.4.
How can you determine whether a binary tree is a subtree of another binary tree?
4.5.
In a binary tree, how do you calculate the distance between two nodes?
5.
Conclusion
Last Updated: Mar 27, 2024

Replace Every Node of an N-ary Tree with the Sum of all its Subtrees

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

We all have a wish to crack the interviews of top MNCs to be able to work there. To fulfill our dream, we need to ace data structures and algorithms, and in order to do that, an understanding of Trees and Graphs is necessary. 

The N-ary tree data structure is a complex binary tree data structure that allows us to have multiple children at each node, similar to the binary tree data structure, but with n number of children. In this blog, we will learn how to replace every node of the N-ary Tree with the sum of all its subtrees, which will eventually increase your familiarity with trees.

Let’s begin to understand the task with the below statement.

Problem Statement:

An N-ary tree is given. The task is to replace every node value with the sum of all the node values in its subtrees.

Example: 

This is the sample example:-

Input

 

Preorder-Traversal: {1, 2, 5, 6, 3, 4}

Output

 

Preorder-Traversal: {20, 13, 5, 6, 3, 4}

Explanation

Every node is replaced by the sum of nodes of its subtrees.

Intuition

It is always important to get an intuition in an interview after the problem is given. Intuition guides you to put your first step to reach the solution. There is no way other than practice to get an intuition every time you understand a problem.

In this problem, the intuition that will help us to reach the solution is that the leaf nodes do not have any child, so we can always start from the leaf nodes and then proceed to its parents until the root comes. This solution with the use of recursion will be cost-effective as well as time-effective.

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

Approach

In the current node, we need to store the sum of each node in its subtree. Since leaf nodes do not have any children, so it will always be an excellent choice to start from the leaf nodes and then move to their parents. In this way, we can recursively reach the root.

Therefore, having the root of the tree, we can first replace the children with its subtree sum, and after that, we can simply add on all the values stored in the children nodes with the value of the current node to get the sum of its subtree. Thus, we can replace the whole tree with the sum of its subtree nodes. 

The solution can be understood with the below algorithm.

Algorithm

  • The function replaceSubtreeSum(Node* root) will take the current node as input and return the sum of its subtree.
     
  • First, we will check if the ‘root’ is a NULL pointer. If yes, the subtree sum will be zero.
     
  • We will iterate through the children of the ‘root’ and call replaceSubtreeSum(), with the current child as the ‘root,’ so that its value gets replaced with its subtree sum.
     
  • Now we will take the sum of all the child values along with the ‘root’ value and finally replace it with the current ‘root’ value. 
     

Below is the program with this algorithm.

Program

// C++ program to replace values with the sum of subtree.
#include <iostream>

using namespace std;

// Structure for the node of the N-ary tree.
typedef struct Node
{
      // Value of the node.
      int value;
      // Number of children of the current node.
      int numChild;
      // Array containing pointers to children.
      Node** children;

      // Default constructor.
      Node()
      {
            value = 0;
            numChild = 0;
      }

      // Constructor.
      Node(int len, int data)
      {
            value = data;
            children = new Node*();
            numChild = len;
      }
} Node;

// Function to replace the value of N-ary tree with the subtree sum.
int replaceSubtreeSum(Node* root)
{
      // Checking if the root is null.
      if (!root)
            return 0;

      // Iterating through the array of children.
      for (int i = 0; i < root->numChild; i++)
      {
            // Storing the subtree sum of children.
            root->value += replaceSubtreeSum(root->children[i]);
      }

      // Returning the sum of nodes in the root's subtree.
      return root->value;
}

// Function for preorder traversal of the N-ary tree.
void preorder(Node* root)
{
      if (!root)
            return;
      cout << root->value << " ";
      for (int i = 0; i < root->numChild; i++)
            preorder(root->children[i]);
}

// Main Function.
int main()
{
    /* Generating the following N-ary Tree.

              1
          /  |   \
          6   8    5
        / | \
      2  7  3

      Root of the Tree.*/      
Node *root = new Node(3, 1);
      root->children[0] = new Node(3, 6);
      root->children[1] = new Node(3, 8);
      root->children[2] = new Node(3, 5);
      root->children[0]->children[0] = new Node(3, 2);
      root->children[0]->children[1] = new Node(3, 7);
      root->children[0]->children[2] = new Node(3, 3);

      // Printing preorder traversal before replacements.
      cout << "Preorder Traversal before replacements: ";
      preorder(root);

      // Calling the function for replacements.
      replaceSubtreeSum(root);

      // Printing preorder traversal after replacements.
      cout << endl << "Preorder Traversal after replacements: ";
      preorder(root);

      return 0;
}

Output

Preorder Traversal before replacements: 1 6 2 7 3 8 5 

Preorder Traversal after replacements: 32 18 2 7 3 8 5

Time Complexity

O(N), where ‘N’ is the number of total nodes in the N-ary tree.

Explanation: As we recursively go through each node only once, there are in total n calls being made, so O(N).

Space complexity

O(N), where ‘N’ is the number of tota nodes in the N-ary tree.

Explanation: ‘N’ number of nodes used to store the data of the N-ary tree constitutes a total space of O(N).

Frequently Asked Questions

What are some real-world applications of the Binary Tree data structure?

One of the most common data structures is the binary tree. It also serves as a foundation for a variety of additional user-defined data structures. This data structure and its implementation are used in a variety of real-world applications, either directly or indirectly. Many compression algorithms, such as Huffman coding, are implemented using binary trees. In networking, binary trees are also employed. Internally, binary trees are also used by decision trees. Binary trees are used to implement priority queues in heap data structures.

What is the Red-Black tree data structure?

The Red-Black Tree is a unique self-balancing tree that possesses the following characteristics: each Node is either red or black in color, the root is always black in color, there can't be a red parent or red child for a red node, the number of black nodes on each path from the root node to a NULL node is the same.

How can you determine whether a binary tree is a subtree of another binary tree?

You've been given two binary trees and must determine whether one of them is a subtree of the other. A binary tree subtree A node from BT and all of its descendants make up BT, which is a tree T. T1 is a subtree of binary tree BT in the following example.

How can you determine whether a binary tree is a subtree of another binary tree?

Let's say we have a binary tree called T. We'll now see if a binary tree S is a subtree of T. To begin, look to see if there is a node in T that is also in S. Once you've located this common node, see if the nodes below are also part of S. If this is the case, we can reasonably conclude that S is a subtree of T.

In a binary tree, how do you calculate the distance between two nodes?

Consider two binary tree nodes, n1, and n2, respectively. The least number of edges that must be crossed to get from one node to the other is equal to the distance between n1 and n2. It's crucial to remember that you travel the shortest path between the nodes.

Conclusion

The above blog has covered an important interview question frequently asked in big MNCs where Data Structures and Algorithms play an important role. Replacing every Node of an N-ary Tree with the sum of all its subtrees is a good question related to trees, which enhances your understanding of the traversal of trees from root to leaves. It also helps us to learn the way to obtain the sum of the subtree of the current Node.

Also check out - Inorder Predecessor

Find more such interesting questions on our practice platform Coding Ninjas Studio if you want to learn more before jumping into practicing, head over to our library section for many such interesting blogs. Keep learning.

Happy Coding!

Previous article
Replace each node in a binary tree with the sum of its inorder predecessor and successor
Next article
Perfect Binary Tree Specific Level Order Traversal
Live masterclass