Given a Prufer sequence, the task is to find the degrees of all the nodes of the tree made by the prufer sequence.
Examples:
Input: arr[] = {4, 1, 3, 4}
Output: 2 1 2 3 1 1
The tree is:
2----4----3----1----5
|
6
Input: arr[] = {1, 2, 2}
Output: 2 3 1 1 1
A simple approach is to create the tree using the Prufer sequence and then find the degree of all the nodes.
Efficient approach: Create a degree[] array of size 2 more than the length of the prufer sequence, since the length of prufer sequence is N – 2 if N is the number of nodes. Initially, fill the degree array with 1. Iterate in the Prufer sequence and increase the frequency in the degree table for every element. This method works because the frequency of a node in the Prufer sequence is one less than the degree in the tree.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to print the degrees of every// node in the tree made by// the given Prufer sequencevoid printDegree(int prufer[], int n){ int node = n + 2; // Hash-table to mark the // degree of every node int degree[n + 2 + 1]; // Initially let all the degrees be 1 for (int i = 1; i <= node; i++) degree[i] = 1; // Increase the count of the degree for (int i = 0; i < n; i++) degree[prufer[i]]++; // Print the degree of every node for (int i = 1; i <= node; i++) { cout << degree[i] << " "; }}// Driver codeint main(){ int a[] = { 4, 1, 3, 4 }; int n = sizeof(a) / sizeof(a[0]); printDegree(a, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG { // Function to print the degrees of every // node in the tree made by // the given Prufer sequence static void printDegree(int prufer[], int n) { int node = n + 2; // Hash-table to mark the // degree of every node int[] degree = new int[n + 2 + 1]; // Initially let all the degrees be 1 for (int i = 1; i <= node; i++) { degree[i] = 1; } // Increase the count of the degree for (int i = 0; i < n; i++) { degree[prufer[i]]++; } // Print the degree of every node for (int i = 1; i <= node; i++) { System.out.print(degree[i] + " "); } } // Driver code public static void main(String[] args) { int a[] = {4, 1, 3, 4}; int n = a.length; printDegree(a, n); }}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 implementation of the approach # Function to print the degrees of # every node in the tree made by # the given Prufer sequence def printDegree(prufer, n): node = n + 2 # Hash-table to mark the # degree of every node degree = [1] * (n + 2 + 1) # Increase the count of the degree for i in range(0, n): degree[prufer[i]] += 1 # Print the degree of every node for i in range(1, node+1): print(degree[i], end = " ") # Driver code if __name__ == "__main__": a = [4, 1, 3, 4] n = len(a) printDegree(a, n) # This code is contributed by Rituraj Jain |
C#
// C# implementation of the approachusing System; class GFG {// Function to print the degrees of every// node in the tree made by// the given Prufer sequencestatic void printDegree(int []prufer, int n) { int node = n + 2; // Hash-table to mark the // degree of every node int[] degree = new int[n + 2 + 1]; // Initially let all the degrees be 1 for (int i = 1; i <= node; i++) { degree[i] = 1; } // Increase the count of the degree for (int i = 0; i < n; i++) { degree[prufer[i]]++; } // Print the degree of every node for (int i = 1; i <= node; i++) { Console.Write(degree[i] + " "); }}// Driver codepublic static void Main(String[] args) { int []a = {4, 1, 3, 4}; int n = a.Length; printDegree(a, n);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the approach // Function to print the degrees of every // node in the tree made by // the given Prufer sequence function printDegree(prufer , n) { var node = n + 2; // Hash-table to mark the // degree of every node var degree = Array(n + 2 + 1).fill(0); // Initially let all the degrees be 1 for (i = 1; i <= node; i++) { degree[i] = 1; } // Increase the count of the degree for (i = 0; i < n; i++) { degree[prufer[i]]++; } // Print the degree of every node for (i = 1; i <= node; i++) { document.write(degree[i] + " "); } } // Driver code var a = [ 4, 1, 3, 4 ]; var n = a.length; printDegree(a, n);// This code contributed by Rajput-Ji</script> |
Output:
2 1 2 3 1 1
Time Complexity: O(N), as we are using a loop to traverse N times. Where N is the number of elements in the array.
Auxiliary Space: O(N), as we are using extra space degree array.
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!
