Given an n-ary Tree having N nodes numbered from 1 to N, the task is to print a list of nodes containing 0, 1, 2, 3, . . ., n children.
Note: An n-ary Tree is a tree in which nodes can have at most n children.
Examples:
Input:
Output:
0 child: 3, 5, 6, 7
1 child: 4
2 child: 2
3 child: 1Input:
Output:
0 child: 15, 30, 40, 99, 22, 46, 56, 25, 90
1 child: 34, 60, 70
2 child: 12, 21
3 child: 50
5 child: 20
Approach: The idea to solve the problem by iterating the tree using level order traversal.
Follow the steps mentioned below to solve the problem:
- Traverse from i = 1 to N:
- For each node use level order traversal to find the location of that value in the tree.
- Upon finding that node, use the list of children and calculate the number of children it has (say X).
- Use a map to add ith node in the list of nodes that have X children.
- Iterate the map and print the nodes having the number of children in the range [0 to n].
Below is the implementation of the above approach :
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Node Classclass Node {public: int key_ele; vector<Node*> child; Node(int data_value) { key_ele = data_value; }};// Function to find number of childint numberOfChild(Node* root, int ele){ int num = 0; if (root == NULL) { return 0; } // Initializing queue data structure queue<Node*> q; q.push(root); while (!q.empty()) { int n = q.size(); while (n > 0) { Node* nn = q.front(); q.pop(); if (nn->key_ele == ele) { num = num + nn->child.size(); return num; } for (int i = 0; i < nn->child.size(); i++) { q.push(nn->child[i]); } n--; } } return num;}// Function to print the nodes// having children in range [0, n]void printTree(Node* root, vector<int> vec){ // map to store nodes // with same number of children map<int, vector<int> > mp; int i = 0; for (i = 0; i < vec.size(); i++) { int temp; temp = numberOfChild(root, vec[i]); mp[temp].push_back(vec[i]); } map<string, int>::iterator iter; for (auto& value : mp) { cout << value.first << " child: "; auto& list = value.second; int len = list.size(); int s = 0; for (auto& element : list) { if (s < len - 1) { cout << element << ", "; } else { cout << element; } s++; } cout << endl; }}// Driver Codeint main(){ vector<int> vec = { 1, 2, 3, 4, 5, 6, 7 }; map<int, vector<int> > mp; vector<int> v; Node* root = new Node(1); (root->child).push_back(new Node(2)); (root->child).push_back(new Node(3)); (root->child).push_back(new Node(4)); (root->child[0]->child).push_back(new Node(5)); (root->child[0]->child).push_back(new Node(6)); (root->child[2]->child).push_back(new Node(7)); // Function call printTree(root, vec); return 0;} |
Java
// Java code for the above approach:import java.util.*;public class Main { static class Node { int key_ele; ArrayList <Node> child; Node(int data_value) { key_ele = data_value; child = new ArrayList <Node> (); } } // Function to find number of child static int numberOfChild(Node root, int ele) { int num = 0; if (root == null) { return 0; } // Initializing queue data structure Queue <Node> q = new LinkedList <> (); q.add(root); while (!q.isEmpty()) { int n = q.size(); while (n > 0) { Node nn = q.peek(); q.remove(); if (nn.key_ele == ele) { num = num + nn.child.size(); return num; } for (int i = 0; i < nn.child.size(); i++) { q.add(nn.child.get(i)); } n--; } } return num; } // Function to print the nodes // having children in range [0, n] static void printTree(Node root, int[] vec) { // HashMap to store nodes // with same number of children HashMap <Integer, ArrayList <Integer> > mp = new HashMap <Integer,ArrayList <Integer>> (); int i = 0; for (i = 0; i < vec.length; i++) { int temp; temp = numberOfChild(root, vec[i]); if(mp.containsKey(temp)){ mp.get(temp).add(vec[i]); } else{ mp.put(temp, new ArrayList <Integer> ()); mp.get(temp).add(vec[i]); } } for (Map.Entry <Integer, ArrayList<Integer> > value : mp.entrySet()) { System.out.print(value.getKey() + " child: "); ArrayList <Integer> list = value.getValue(); int len = list.size(); for (i=0; i < len; i++) { if (i < len - 1) { System.out.print(list.get(i) + ", "); } else { System.out.print(list.get(i)); } } System.out.print("\n"); } } public static void main(String args[]) { int[] vec = { 1, 2, 3, 4, 5, 6, 7 }; HashMap <Integer, ArrayList <Integer> > mp; ArrayList <Integer> v; Node root = new Node(1); (root.child).add(new Node(2)); (root.child).add(new Node(3)); (root.child).add(new Node(4)); (root.child.get(0).child).add(new Node(5)); (root.child.get(0).child).add(new Node(6)); (root.child.get(2).child).add(new Node(7)); // Function call printTree(root, vec); }}// This code has been contributed by Sachin Sahara (sachin801) |
Python3
# Node Classfrom collections import OrderedDictclass Node: def __init__(self, data_value): self.key_ele = data_value self.child = []# Function to find number of childdef numberOfChild(root, ele): num = 0 if root is None: return 0 # Initializing queue data structure q = [] q.append(root) while len(q) > 0: n = len(q) while n > 0: nn = q.pop(0) if nn.key_ele == ele: num += len(nn.child) return num for i in range(len(nn.child)): q.append(nn.child[i]) n -= 1 return num# Function to print the nodes# having children in range [0, n]def printTree(root, vec): # map to store nodes # with same number of children mp = {} for i in range(len(vec)): temp = numberOfChild(root, vec[i]) if temp not in mp: mp[temp] = [] mp[temp].append(vec[i]) mp = OrderedDict(sorted(mp.items())) for key,value in mp.items(): print(f"{key} child: ", end="") len_list = len(value) s = 0 for element in value: if s < len_list - 1: print(element, end=", ") else: print(element, end="") s += 1 print()# Driver Codevec = [1, 2, 3, 4, 5, 6, 7]mp = {}v = []root = Node(1)root.child.append(Node(2))root.child.append(Node(3))root.child.append(Node(4))root.child[0].child.append(Node(5))root.child[0].child.append(Node(6))root.child[2].child.append(Node(7)) # Function callprintTree(root, vec)# This code is contributed by Potta Lokesh |
C#
using System;using System.Collections.Generic;class MainClass { class Node { public int key_ele; public List<Node> child; public Node(int data_value) { key_ele = data_value; child = new List<Node>(); } } static int numberOfChild(Node root, int ele) { int num = 0; if (root == null) { return 0; } Queue<Node> q = new Queue<Node>(); q.Enqueue(root); while (q.Count != 0) { int n = q.Count; while (n > 0) { Node nn = q.Peek(); q.Dequeue(); if (nn.key_ele == ele) { num = num + nn.child.Count; return num; } for (int i = 0; i < nn.child.Count; i++) { q.Enqueue(nn.child[i]); } n--; } } return num; } static void printTree(Node root, int[] vec) { Dictionary<int, List<int> > mp = new Dictionary<int, List<int> >(); int i = 0; for (i = 0; i < vec.Length; i++) { int temp = numberOfChild(root, vec[i]); if (mp.ContainsKey(temp)) { mp[temp].Add(vec[i]); } else { mp.Add(temp, new List<int>()); mp[temp].Add(vec[i]); } } foreach(var value in mp) { Console.Write(value.Key + " child: "); List<int> list = value.Value; int len = list.Count; for (i = 0; i < len; i++) { if (i < len - 1) { Console.Write(list[i] + ", "); } else { Console.Write(list[i]); } } Console.WriteLine(); } } public static void Main(string[] args) { int[] vec = { 1, 2, 3, 4, 5, 6, 7 }; Node root = new Node(1); root.child.Add(new Node(2)); root.child.Add(new Node(3)); root.child.Add(new Node(4)); root.child[0].child.Add(new Node(5)); root.child[0].child.Add(new Node(6)); root.child[2].child.Add(new Node(7)); printTree(root, vec); }} |
Javascript
class Node { constructor(data_value) { this.key_ele = data_value; this.child = []; } } // Function to find number of child function numberOfChild(root, ele) { let num = 0; if (root === null) { return 0; } // Initializing queue data structure let q = []; q.push(root); while (q.length > 0) { let n = q.length; while (n > 0) { let nn = q.shift(); if (nn.key_ele === ele) { num = num + nn.child.length; return num; } for (let i = 0; i < nn.child.length; i++) { q.push(nn.child[i]); } n--; } } return num; } // Function to print the nodes // having children in range [0, n] function printTree(root, vec) { // map to store nodes // with same number of children let mp = new Map(); for (let i = 0; i < vec.length; i++) { let temp = numberOfChild(root, vec[i]); if (!mp.has(temp)) { mp.set(temp, []); } mp.get(temp).push(vec[i]); } for (let value of mp) { console.log(value[0], "child: ", value[1].join(", ")); } } // Driver Code let vec = [1, 2, 3, 4, 5, 6, 7]; let root = new Node(1); root.child.push(new Node(2)); root.child.push(new Node(3)); root.child.push(new Node(4)); root.child[0].child.push(new Node(5)); root.child[0].child.push(new Node(6)); root.child[2].child.push(new Node(7)); // Function call printTree(root, vec); // This code is contributed by aadityamaharshi21. |
Output
0 child: 3, 5, 6, 7 1 child: 4 2 child: 2 3 child: 1
Time Complexity: O(N2)
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!
