Given an array arr[] representing a Generic(N-ary) tree. The task is to replace the node data with the depth(level) of the node. Assume level of root to be 0.
Array Representation: The N-ary tree is serialized in the array arr[] using level order traversal as described below:
- The input is given as a level order traversal of N-ary Tree.
- The first element of the array arr[] is the root node.
- Then, followed by a number N, which denotes the number of children of the previous node. Value zero denotes Null Node.
Examples:
Input: arr[] = { 10, 3, 20, 30, 40, 2, 40, 50, 0, 0, 0, 0 }
Below is the N-ary Tree of the above array level order traversal:
Output:
Below is the representation of the above output:
Input: arr[] = {1, 3, 2, 3, 4, 2, 5, 6, 0, 0, 2, 8, 9}
Below is the N-ary Tree of the above array level order traversal:
Output:
Below is the representation of the above output:
Approach:
- Traverse the tree starting from root.
- While traversing pass depth of node as a parameter.
- Track depth by passing it as 0 for root and (1 + current level) for children.
Below is the implementation of the above approach:
CPP
// C++ program to implement node with// it's depth value#include <bits/stdc++.h>using namespace std;// Treenode class using templatetemplate <typename T>class TreeNode {public: // To store node value T data; // Pointer to TreeNode to store // the child node vector<TreeNode<T>*> children; // Constructor to assign data // to node TreeNode(T data) { this->data = data; } // Destructors to delete a node ~TreeNode() { for (int i = 0; i < children.size(); i++) { delete children[i]; } }};// Function to take input level wise// i.e., in level order traversalTreeNode<int>* takeInputLevelWise(int arr[]){ int idx = 1; // Input root int rootData = arr[0]; // Initialize tree with a root node TreeNode<int>* root = new TreeNode<int>(rootData); // Initialise queue for appending // node as a child of parent in // N-ary tree queue<TreeNode<int>*> pendingNodes; // Push the root node in queue pendingNodes.push(root); // While queue is not empty append // child to the root while (pendingNodes.size() != 0) { // Take the first node TreeNode<int>* front = pendingNodes.front(); pendingNodes.pop(); // Input number of child int numChild = arr[idx]; idx++; for (int i = 0; i < numChild; i++) { int childData = arr[idx]; idx++; // Make child Node TreeNode<int>* child = new TreeNode<int>(childData); // Append child node to // it's parent front->children.push_back(child); pendingNodes.push(child); } } return root;}// Function to print each node data// in level ordervoid printLevelATNewLine(TreeNode<int>* root){ queue<TreeNode<int>*> q; q.push(root); q.push(NULL); while (!q.empty()) { TreeNode<int>* first = q.front(); q.pop(); if (first == NULL) { if (q.empty()) { break; } cout << endl; q.push(NULL); continue; } cout << first->data << " "; for (int i = 0; i < first->children.size(); i++) { q.push(first->children[i]); } }}// Helper function to replace the// node data with their level valuevoid helper(TreeNode<int>* root, int depth){ // Replace the node data with // it's depth root->data = depth; for (int i = 0; i < root->children.size(); i++) { helper(root->children[i], depth + 1); }}// Function to replace with depthvoid replaceWithDepthValue(TreeNode<int>* root){ helper(root, 0);}// Driver Codeint main(){ // Given level order traversal in // the array arr[] int arr[] = { 10, 3, 20, 30, 40, 2, 40, 50, 0, 0, 0, 0 }; // Initialise Tree TreeNode<int>* root; root = takeInputLevelWise(arr); // Function call to replace with // depth value replaceWithDepthValue(root); // Function call to print // in level order printLevelATNewLine(root); return 0;} |
Java
// Java program to replace node with// it's depth value// Importing classes and interfaceimport java.util.ArrayList;import java.util.LinkedList;import java.util.Queue;class GFG { // TreeNode class static class TreeNode<T> { // To store node value T data; // List of TreeNode to store // the child nodes ArrayList<TreeNode<T> > children; // Constructor to assign data to node TreeNode(T data) { this.data = data; children = new ArrayList<TreeNode<T> >(); } } // Function to take input level wise // i.e., in level order traversal static TreeNode<Integer> takeInputLevelWise(int arr[]) { int idx = 1; // Input root int rootData = arr[0]; // Initialize tree with a root node TreeNode<Integer> root = new TreeNode<Integer>(rootData); // Initialize queue for appending // node as a child of parent in // N-ary tree Queue<TreeNode<Integer> > pendingNodes = new LinkedList<TreeNode<Integer> >(); // Push the root node in queue pendingNodes.add(root); // While queue is not empty append // child to the node while (pendingNodes.size() != 0) { // Take the first node TreeNode<Integer> front = pendingNodes.peek(); pendingNodes.poll(); // Input number of its child int numChild = arr[idx]; idx++; for (int i = 0; i < numChild; i++) { int childData = arr[idx]; idx++; // Make child Node TreeNode<Integer> child = new TreeNode<Integer>(childData); // Append child node to // it's parent front.children.add(child); pendingNodes.add(child); } } return root; } // Function to print each node data // in level order static void printLevelATNewLine(TreeNode<Integer> root) { Queue<TreeNode<Integer> > q = new LinkedList<TreeNode<Integer> >(); q.add(root); q.add(null); while (!q.isEmpty()) { TreeNode<Integer> first = q.peek(); q.poll(); if (first == null) { // If there is no more nodes if (q.isEmpty()) { break; } // All the nodes of current level are // visited System.out.println(); q.add(null); continue; } System.out.print(first.data + " "); // Append current node's child to queue for (int i = 0; i < first.children.size(); i++) { q.add(first.children.get(i)); } } } // Helper function to replace the // node data with their level value static void helper(TreeNode<Integer> root, int depth) { // Replace the node data with // it's depth root.data = depth; for (int i = 0; i < root.children.size(); i++) { helper(root.children.get(i), depth + 1); } } // Function to replace with depth static void replaceWithDepthValue(TreeNode<Integer> root) { helper(root, 0); } // Driver Code public static void main(String[] args) { // Given level order traversal in // the array arr[] int arr[] = { 10, 3, 20, 30, 40, 2, 40, 50, 0, 0, 0, 0 }; // Initialise Tree TreeNode<Integer> root; root = takeInputLevelWise(arr); // Function call to replace with // depth value replaceWithDepthValue(root); // Function call to print // in level order printLevelATNewLine(root); }}// This code is contributed by jainlovely450 |
Python3
# Python code for the above approachfrom typing import List, Tuple# TreeNode classclass TreeNode: # To store node value data: int # List of TreeNode to store # the child nodes children: List['TreeNode'] # Constructor to assign data to node def __init__(self, data: int): self.data = data self.children = []# Function to take input level wise# i.e., in level order traversaldef take_input_level_wise(arr: List[int]) -> TreeNode: idx = 1 # Input root root_data = arr[0] # Initialize tree with a root node root = TreeNode(root_data) # Initialize queue for appending # node as a child of parent in # N-ary tree pending_nodes = [root] # While queue is not empty append # child to the node while pending_nodes: # Take the first node front = pending_nodes[0] pending_nodes = pending_nodes[1:] # Input number of its child num_child = arr[idx] idx += 1 for i in range(num_child): child_data = arr[idx] idx += 1 # Make child Node child = TreeNode(child_data) # Append child node to # it's parent front.children.append(child) pending_nodes.append(child) return root# Function to print each node data# in level orderdef print_level_at_new_line(root: TreeNode): q = [root] q.append(None) while q: first = q[0] q = q[1:] if first is None: # If there is no more nodes if not q: break # All the nodes of current level are # visited print() q.append(None) continue print(first.data, end=' ') # Append current node's child to queue for i in range(len(first.children)): q.append(first.children[i])# Helper function to replace the# node data with their level valuedef helper(root: TreeNode, depth: int): # Replace the node data with # it's depth root.data = depth for i in range(len(root.children)): helper(root.children[i], depth + 1)# Function to replace with depthdef replace_with_depth_value(root: TreeNode): helper(root, 0)# Driver Codeif __name__ == '__main__': # Given level order traversal in # the array arr[] arr = [10, 3, 20, 30, 40, 2, 40, 50, 0, 0, 0, 0] # Initialise Tree root = take_input_level_wise(arr) # Function call to replace with # depth value replace_with_depth_value(root) # Print the tree in level order print_level_at_new_line(root) # This code is contributed by Potta Lokesh |
C#
using System;using System.Collections.Generic;// Class to represent a node with data and its children in// N-ary treeclass TreeNode<T> { public T Data { get; set; } public List<TreeNode<T> > Children { get; set; } public TreeNode(T data) { this.Data = data; this.Children = new List<TreeNode<T> >(); }}class GFG { static void Main(string[] args) { // Input level order data int[] arr = { 10, 3, 20, 30, 40, 2, 40, 50, 0, 0, 0, 0 }; // Initialize Tree with root node var root = TakeInputLevelWise(arr); // Replace the node data with their depth value ReplaceWithDepthValue(root, 0); // Print level order PrintLevelAtNewLine(root); } // Function to take input level wise static TreeNode<int> TakeInputLevelWise(int[] arr) { int idx = 1; // Input root data int rootData = arr[0]; var root = new TreeNode<int>(rootData); // Initialise queue for appending node as a child of // parent var pendingNodes = new Queue<TreeNode<int> >(); // Push the root node in queue pendingNodes.Enqueue(root); // While queue is not empty append child to the root while (pendingNodes.Count != 0) { // Take the first node var front = pendingNodes.Dequeue(); // Input number of children int numChild = arr[idx]; idx++; for (int i = 0; i < numChild; i++) { int childData = arr[idx]; idx++; // Make child node var child = new TreeNode<int>(childData); // Append child node to its parent front.Children.Add(child); pendingNodes.Enqueue(child); } } return root; } // Function to print level order static void PrintLevelAtNewLine(TreeNode<int> root) { var q = new Queue<TreeNode<int> >(); q.Enqueue(root); q.Enqueue(null); while (q.Count != 0) { var first = q.Dequeue(); if (first == null) { if (q.Count == 0) { break; } Console.WriteLine(); q.Enqueue(null); continue; } Console.Write(first.Data + " "); foreach(var child in first.Children) { q.Enqueue(child); } } } // Function to replace node data with their depth value static void ReplaceWithDepthValue(TreeNode<int> root, int depth) { root.Data = depth; foreach(var child in root.Children) { ReplaceWithDepthValue(child, depth + 1); } }}//This Code is Contributed by chinmaya121221 |
Javascript
// JavaScript program to replace node with it's depth value// TreeNode classclass TreeNode { constructor(data) { // To store node value this.data = data; // List of TreeNode to store the child nodes this.children = []; }}// Function to take input level wise i.e., in level order traversalfunction takeInputLevelWise(arr) { let idx = 1; // Input root let rootData = arr[0]; // Initialize tree with a root node const root = new TreeNode(rootData); // Initialize queue for appending node as a child of parent in N-ary tree const pendingNodes = []; // Push the root node in queue pendingNodes.push(root); // While queue is not empty append child to the node while (pendingNodes.length !== 0) { // Take the first node const front = pendingNodes.shift(); // Input number of its child const numChild = arr[idx]; idx++; for (let i = 0; i < numChild; i++) { const childData = arr[idx]; idx++; // Make child Node const child = new TreeNode(childData); // Append child node to it's parent front.children.push(child); pendingNodes.push(child); } } return root;}// Function to print each node data in level orderfunction printLevelATNewLine(root) { const q = []; q.push(root); q.push(null); while (q.length !== 0) { const first = q.shift(); if (first === null) { // If there is no more nodes if (q.length === 0) { break; } // All the nodes of current level are visited console.log("<br>"); q.push(null); continue; } console.log(first.data + " "); // Append current node's child to queue for (let i = 0; i < first.children.length; i++) { q.push(first.children[i]); } }}// Helper function to replace the node data with their level valuefunction helper(root, depth) { // Replace the node data with it's depth root.data = depth; for (let i = 0; i < root.children.length; i++) { helper(root.children[i], depth + 1); }}// Function to replace with depthfunction replaceWithDepthValue(root) { helper(root, 0);}// Given level order traversal in the array arr[]const arr = [10, 3, 20, 30, 40, 2, 40, 50, 0, 0, 0, 0];// Initialise Treelet root = takeInputLevelWise(arr);// Function call to replace with depth valuereplaceWithDepthValue(root);// Function call to print in level orderprintLevelATNewLine(root);// This code is contributed by sankar. |
Output
0 1 1 1 2 2
Time Complexity: O(N), where N is the number of nodes in Tree.
Auxiliary Space: O(N), where N is the number of nodes in Tree.
Another Approach: We can also replace the node’s value with its depth while creating the tree. We are traversing the array level wise which means that nodes currently present in the queue are of the same depth. As we append its child nodes to the queue, they will be present in the next level. We can initialize a variable as current depth equal to 1 and when we create child node we can assign its value to current depth level. After traversing all the nodes present in the current level we will increment current depth level by 1.
C++
// C++ program to implement node with// it's depth value#include <bits/stdc++.h>using namespace std;// Treenode class using templatetemplate <typename T> class TreeNode {public: // To store node value T data; // Pointer to TreeNode to store // the child node vector<TreeNode<T>*> children; // Constructor to assign data // to node TreeNode(T data) { this->data = data; } // Destructors to delete a node ~TreeNode() { for (int i = 0; i < children.size(); i++) { delete children[i]; } }};// Function to take input level wise// i.e., in level order traversalTreeNode<int>* takeInputLevelWise(int arr[]){ int idx = 1; int depthLevel = 1; // Initialize tree with a root node // with depth 0 TreeNode<int>* root = new TreeNode<int>(0); // Initialise queue for appending // node as a child of parent in // N-ary tree queue<TreeNode<int>*> pendingNodes; // Push the root node in queue pendingNodes.push(root); // While queue is not empty append // child to the node while (pendingNodes.size() != 0) { // Number of nodes present in the current level int size = pendingNodes.size(); while (size > 0) { // Take the first node TreeNode<int>* front = pendingNodes.front(); pendingNodes.pop(); // Input number of its child int numChild = arr[idx]; idx++; for (int i = 0; i < numChild; i++) { idx++; // Make child Node and assign its data // value equal to depthLevel TreeNode<int>* child = new TreeNode<int>(depthLevel); // Append child node to // it's parent front->children.push_back(child); pendingNodes.push(child); } size--; } // Increment depth level depthLevel++; } return root;}// Function to print each node data// in level ordervoid printLevelATNewLine(TreeNode<int>* root){ queue<TreeNode<int>*> q; q.push(root); q.push(NULL); while (!q.empty()) { TreeNode<int>* first = q.front(); q.pop(); if (first == NULL) { // If there is no more nodes to visit if (q.empty()) { break; } // All the nodes of current level are visited cout << endl; q.push(NULL); continue; } cout << first->data << " "; // Append current node's child to queue for (int i = 0; i < first->children.size(); i++) { q.push(first->children[i]); } }}// Driver Codeint main(){ // Given level order traversal in // the array arr[] int arr[] = { 10, 3, 20, 30, 40, 2, 40, 50, 0, 0, 0, 0 }; // Initialise Tree TreeNode<int>* root; root = takeInputLevelWise(arr); // Function call to print // in level order printLevelATNewLine(root); return 0;}// This code is contributed by jainlovely450 |
Java
// Java program to implement node with// it's depth value// Importing classes and interfaceimport java.util.ArrayList;import java.util.LinkedList;import java.util.Queue;public class GFG { // TreeNode class static class TreeNode<T> { // To store node value T data; // List of TreeNode to store // the child nodes ArrayList<TreeNode<T> > children; // Constructor to assign data to node TreeNode(T data) { this.data = data; children = new ArrayList<TreeNode<T> >(); } } // Function to take input level wise // i.e., in level order traversal and // assign value of node equal to its depth static TreeNode<Integer> takeInputLevelWise(int arr[]) { int idx = 1; int depthLevel = 1; // Initialize tree with a root node // with depth 0 TreeNode<Integer> root = new TreeNode<Integer>(0); // Initialize queue for appending // node as a child of parent in // N-ary tree Queue<TreeNode<Integer> > pendingNodes = new LinkedList<TreeNode<Integer> >(); // Push the root node in queue pendingNodes.add(root); // While queue is not empty append // child to the node while (!pendingNodes.isEmpty()) { // Number of nodes present in the current level int size = pendingNodes.size(); while (size > 0) { TreeNode<Integer> front = pendingNodes.peek(); pendingNodes.poll(); // Input number of child int numChild = arr[idx]; idx++; for (int i = 0; i < numChild; i++) { idx++; // Make child Node and assign its data // value equal to depthLevel TreeNode<Integer> child = new TreeNode<Integer>(depthLevel); // Append child node to // it's parent front.children.add(child); pendingNodes.add(child); } size--; } // Increment depth level depthLevel++; } return root; } // Function to print each node data // in level order static void printLevelATNewLine(TreeNode<Integer> root) { Queue<TreeNode<Integer> > q = new LinkedList<TreeNode<Integer> >(); q.add(root); q.add(null); while (!q.isEmpty()) { TreeNode<Integer> first = q.peek(); q.poll(); if (first == null) { // If there is no more nodes to visit if (q.isEmpty()) { break; } // All the nodes of current level are // visited System.out.println(); q.add(null); continue; } System.out.print(first.data + " "); // Append current node's child to queue for (int i = 0; i < first.children.size(); i++) { q.add(first.children.get(i)); } } } // Driver Code public static void main(String[] args) { // Given level order traversal in // the array arr[] int arr[] = { 10, 3, 20, 30, 40, 2, 40, 50, 0, 0, 0, 0 }; // Initialize Tree TreeNode<Integer> root; root = takeInputLevelWise(arr); // Function call to print // in level order printLevelATNewLine(root); }}// This code is contributed by jainlovely450 |
Python3
# Python code# TreeNode classclass TreeNode: # To store node value def __init__(self, data): self.data = data # List of TreeNode to store # the child nodes self.children = []# Function to take input level wise# i.e., in level order traversal and# assign value of node equal to its depthdef takeInputLevelWise(arr): idx = 1 depthLevel = 1 # Initialize tree with a root node # with depth 0 root = TreeNode(0) # Initialize queue for appending # node as a child of parent in # N-ary tree pendingNodes = [] pendingNodes.append(root) # While queue is not empty append # child to the node while pendingNodes: # Number of nodes present in the current level size = len(pendingNodes) while size > 0: front = pendingNodes[0] pendingNodes.pop(0) # Input number of child numChild = arr[idx] idx += 1 for i in range(numChild): idx += 1 # Make child Node and assign its data # value equal to depthLevel child = TreeNode(depthLevel) # Append child node to # it's parent front.children.append(child) pendingNodes.append(child) size -= 1 # Increment depth level depthLevel += 1 return root# Function to print each node data# in level orderdef printLevelATNewLine(root): q = [] q.append(root) q.append(None) while q: first = q[0] q.pop(0) if first is None: # If there is no more nodes to visit if not q: break # All the nodes of current level are # visited print() q.append(None) continue print(first.data, end=" ") # Append current node's child to queue for i in range(len(first.children)): q.append(first.children[i])# Driver Codeif __name__ == '__main__': # Given level order traversal in # the array arr[] arr = [10, 3, 20, 30, 40, 2, 40, 50, 0, 0, 0, 0] # Initialize Tree root = takeInputLevelWise(arr) # Function call to print # in level order printLevelATNewLine(root) |
C#
// C# program to implement node with it's depth valueusing System;using System.Collections.Generic;public class GFG { // TreeNode class class TreeNode<T> { // To store node value public T data; // List of TreeNode to store // the child nodes public List<TreeNode<T> > children; // Constructor to assign data to node public TreeNode(T data) { this.data = data; children = new List<TreeNode<T> >(); } } // Function to take input level wise i.e., in level // order traversal and assign value of node equal to its // depth static TreeNode<int> takeInputLevelWise(int[] arr) { int idx = 1; int depthLevel = 1; // Initialize tree with a root node with depth 0 TreeNode<int> root = new TreeNode<int>(0); // Initialize queue for appending node as a child of // parent in N-ary tree Queue<TreeNode<int> > pendingNodes = new Queue<TreeNode<int> >(); // Push the root node in queue pendingNodes.Enqueue(root); // While queue is not empty append child to the node while (pendingNodes.Count != 0) { // Number of nodes present in the current level int size = pendingNodes.Count; while (size > 0) { TreeNode<int> front = pendingNodes.Peek(); pendingNodes.Dequeue(); // Input number of child int numChild = arr[idx]; idx++; for (int i = 0; i < numChild; i++) { idx++; // Make child Node and assign its data // value equal to depthLevel TreeNode<int> child = new TreeNode<int>(depthLevel); // Append child node to it's parent front.children.Add(child); pendingNodes.Enqueue(child); } size--; } // Increment depth level depthLevel++; } return root; } // Function to print each node data in level order static void printLevelATNewLine(TreeNode<int> root) { Queue<TreeNode<int> > q = new Queue<TreeNode<int> >(); q.Enqueue(root); q.Enqueue(null); while (q.Count != 0) { TreeNode<int> first = q.Peek(); q.Dequeue(); if (first == null) { // If there is no more nodes to visit if (q.Count == 0) { break; } // All the nodes of current level are // visited Console.WriteLine(); q.Enqueue(null); continue; } Console.Write(first.data + " "); // Append current node's child to queue for (int i = 0; i < first.children.Count; i++) { q.Enqueue(first.children[i]); } } } static public void Main() { // Code // Given level order traversal in the array arr[] int[] arr = { 10, 3, 20, 30, 40, 2, 40, 50, 0, 0, 0, 0 }; // Initialize Tree TreeNode<int> root; root = takeInputLevelWise(arr); // Function call to print in level order printLevelATNewLine(root); }}// This code is contributed by karthik. |
Javascript
<script>// JavaScript program to implement node with// it's depth value// TreeNode classclass TreeNode { // To store node value constructor(data) { this.data = data; // List of TreeNode to store // the child nodes this.children = []; }}// Function to take input level wise// i.e., in level order traversal and// assign value of node equal to its depthfunction takeInputLevelWise(arr) { let idx = 1; let depthLevel = 1; // Initialize tree with a root node // with depth 0 const root = new TreeNode(0); // Initialize queue for appending // node as a child of parent in // N-ary tree const pendingNodes = []; // Push the root node in queue pendingNodes.push(root); // While queue is not empty append // child to the node while (pendingNodes.length !== 0) { // Number of nodes present in the current level let size = pendingNodes.length; while (size > 0) { const front = pendingNodes.shift(); // Input number of child const numChild = arr[idx]; idx++; for (let i = 0; i < numChild; i++) { idx++; // Make child Node and assign its data // value equal to depthLevel const child = new TreeNode(depthLevel); // Append child node to // it's parent front.children.push(child); pendingNodes.push(child); } size--; } // Increment depth level depthLevel++; } return root;}// Function to print each node data// in level orderfunction printLevelATNewLine(root) { const q = []; q.push(root); q.push(null); while (q.length !== 0) { const first = q.shift(); if (first === null) { // If there is no more nodes to visit if (q.length === 0) { break; } // All the nodes of current level are // visited document.write("<br>"); q.push(null); continue; } document.write(first.data + " "); // Append current node's child to queue for (let i = 0; i < first.children.length; i++) { q.push(first.children[i]); } } document.write("<br>")}// Given level order traversal in// the array arr[]const arr = [10, 3, 20, 30, 40, 2, 40, 50, 0, 0, 0, 0];// Initialize Treeconst root = takeInputLevelWise(arr);// Function call to print// in level orderprintLevelATNewLine(root);// This code is contributed by karthik.</script> |
Output
0 1 1 1 2 2
Time Complexity: O(N), where N is the number of nodes in Tree.
Auxiliary Space: O(N), where N is the number of nodes in Tree.
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!
