Given an N-ary tree. The task is to replace the values of each node with the sum of all its subtrees and the node itself.
Examples
Input: 1
/ | \
2 3 4
/ \ \
5 6 7
Output: Initial Pre-order Traversal: 1 2 5 6 7 3 4
Final Pre-order Traversal: 28 20 5 6 7 3 4
Explanation: Value of each node is replaced by the sum of all its subtrees and the node itself.Input: 1
/ | \
4 2 3
/ \ \
7 6 5
Output: Initial Pre-order Traversal: 1 4 7 6 3 5
Final Pre-order Traversal: 23 13 7 6 28 5
Approach: This problem can be solved by using Recursion. Follow the steps below to solve the given problem.
- The easiest way to do this problem is by using recursion.
- Start with the base condition when the current node equals NULL then return 0, as it means it is the leaf node.
- Otherwise, make a recursion call to all its child nodes by traversing using a loop and add the sum of all child nodes in it.
- At last return the current node’s data.
- In this way, all the node’s values will be replaced by the sum of all the subtrees and itself.
Below is the implementation of the above approach.
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Class for the node of the treestruct Node { int data; // List of children struct Node** children; int length; Node() { length = 0; data = 0; } Node(int n, int data_) { children = new Node*(); length = n; data = data_; }};// Function to replace node with// sum of its left subtree, right// subtree and its sumint sumReplacementNary(Node* node){ if (node == NULL) return 0; // Total children count int total = node->length; // Taking sum of all the nodes for (int i = 0; i < total; i++) node->data += sumReplacementNary(node->children[i]); return node->data;}void preorderTraversal(Node* node){ if (node == NULL) return; // Total children count int total = node->length; // Print the current node's data cout << node->data << " "; // All the children except the last for (int i = 0; i < total - 1; i++) preorderTraversal(node->children[i]); // Last child preorderTraversal(node->children[total - 1]);}// Driver codeint main(){ /* Create the following tree 1 / | \ 2 3 4 / \ \ 5 6 7 */ int N = 3; Node* root = new Node(N, 1); root->children[0] = new Node(N, 2); root->children[1] = new Node(N, 3); root->children[2] = new Node(N, 4); root->children[0]->children[0] = new Node(N, 5); root->children[0]->children[1] = new Node(N, 6); root->children[0]->children[2] = new Node(N, 7); cout << "Initial Pre-order Traversal: "; preorderTraversal(root); cout << endl; cout << "Final Pre-order Traversal: "; sumReplacementNary(root); preorderTraversal(root); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{ // Class for the node of the tree static class Node { int data; // List of children Node []children; int length; Node() { length = 0; data = 0; } Node(int n, int data_) { children = new Node[n]; length = n; data = data_; } }; // Function to replace node with // sum of its left subtree, right // subtree and its sum static int sumReplacementNary(Node node) { if (node == null) return 0; // Total children count int total = node.length; // Taking sum of all the nodes for (int i = 0; i < total; i++) node.data += sumReplacementNary(node.children[i]); return node.data; } static void preorderTraversal(Node node) { if (node == null) return; // Total children count int total = node.length; // Print the current node's data System.out.print(node.data+ " "); // All the children except the last for (int i = 0; i < total - 1; i++) preorderTraversal(node.children[i]); // Last child preorderTraversal(node.children[total - 1]); } // Driver code public static void main(String[] args) { /* Create the following tree 1 / | \ 2 3 4 / \ \ 5 6 7 */ int N = 3; Node root = new Node(N, 1); root.children[0] = new Node(N, 2); root.children[1] = new Node(N, 3); root.children[2] = new Node(N, 4); root.children[0].children[0] = new Node(N, 5); root.children[0].children[1] = new Node(N, 6); root.children[0].children[2] = new Node(N, 7); System.out.print("Initial Pre-order Traversal: "); preorderTraversal(root); System.out.println(); System.out.print("Final Pre-order Traversal: "); sumReplacementNary(root); preorderTraversal(root); }} |
Python3
# Python implementation of the approach# Class for the node of the treeclass Node: def __init__(self, data): self.data = data self.children = []# Function to replace node with# sum of its left subtree, right# subtree and its sumdef sumReplacementNary(node): if (node == None): return 0 # Total children count total = len(node.children) # Taking sum of all the nodes for i in range(0, total): node.data += sumReplacementNary(node.children[i]) return node.datadef preorderTraversal(node): if (node == None): return # Total children count total = len(node.children) # Print the current node's data print(node.data, end=" ") # All the children except the last for i in range(0, total): preorderTraversal(node.children[i])# Driver code# Create the following tree# 1# / | \# 2 3 4# / \ \# 5 6 7root = Node(1)root.children.append(Node(2))root.children.append(Node(3))root.children.append(Node(4))root.children[0].children.append(Node(5))root.children[0].children.append(Node(6))root.children[0].children.append(Node(7))print("Initial Pre-order Traversal: ")preorderTraversal(root)print("\n")print("Final Pre-order Traversal: ")sumReplacementNary(root)preorderTraversal(root) |
C#
// C# implementation of the approachusing System;public class GFG{ // Class for the node of the tree class Node { public int data; // List of children public Node []children; public int length; public Node() { length = 0; data = 0; } public Node(int n, int data_) { children = new Node[n]; length = n; data = data_; } }; // Function to replace node with // sum of its left subtree, right // subtree and its sum static int sumReplacementNary(Node node) { if (node == null) return 0; // Total children count int total = node.length; // Taking sum of all the nodes for (int i = 0; i < total; i++) node.data += sumReplacementNary(node.children[i]); return node.data; } static void preorderTraversal(Node node) { if (node == null) return; // Total children count int total = node.length; // Print the current node's data Console.Write(node.data+ " "); // All the children except the last for (int i = 0; i < total - 1; i++) preorderTraversal(node.children[i]); // Last child preorderTraversal(node.children[total - 1]); } // Driver code public static void Main(String[] args) { /* Create the following tree 1 / | \ 2 3 4 / \ \ 5 6 7 */ int N = 3; Node root = new Node(N, 1); root.children[0] = new Node(N, 2); root.children[1] = new Node(N, 3); root.children[2] = new Node(N, 4); root.children[0].children[0] = new Node(N, 5); root.children[0].children[1] = new Node(N, 6); root.children[0].children[2] = new Node(N, 7); Console.Write("Initial Pre-order Traversal: "); preorderTraversal(root); Console.WriteLine(); Console.Write("Final Pre-order Traversal: "); sumReplacementNary(root); preorderTraversal(root); }} |
Javascript
<script> // JavaScript code for the above approach // Class for the node of the tree class Node { // List of children constructor(n = 0, data_ = 0) { this.children = new Array(10000); this.length = n; this.data = data_; } } // Function to replace node with // sum of its left subtree, right // subtree and its sum function sumReplacementNary(node) { if (node == null) return 0; // Total children count let total = node.length; // Taking sum of all the nodes for (let i = 0; i < total; i++) node.data += sumReplacementNary(node.children[i]); return node.data; } function preorderTraversal(node) { if (node == null) return; // Total children count let total = node.length; // Print the current node's data document.write(node.data + " "); // All the children except the last for (let i = 0; i < total - 1; i++) preorderTraversal(node.children[i]); // Last child preorderTraversal(node.children[total - 1]); } // Driver code /* Create the following tree 1 / | \ 2 3 4 / \ \ 5 6 7 */ let N = 3; let root = new Node(N, 1); root.children[0] = new Node(N, 2); root.children[1] = new Node(N, 3); root.children[2] = new Node(N, 4); root.children[0].children[0] = new Node(N, 5); root.children[0].children[1] = new Node(N, 6); root.children[0].children[2] = new Node(N, 7); document.write("Initial Pre-order Traversal: "); preorderTraversal(root); document.write('<br>') document.write("Final Pre-order Traversal: "); sumReplacementNary(root); preorderTraversal(root); </script> |
Output
Initial Pre-order Traversal: 1 2 5 6 7 3 4 Final Pre-order Traversal: 28 20 5 6 7 3 4
Time Complexity: O(N), Where N is the number of nodes in the tree.
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
