Given a Prufer sequence of N integers, the task is to check if the given sequence is a valid Prufer sequence or not.
Examples:
Input: arr[] = {4, 1, 3, 4}
Output: Valid
The tree is:
2----4----3----1----5
|
6
Input: arr[] = {4, 1, 7, 4}
Output: Invalid
Approach: Since we know the Prufer sequence is of length N – 2 where N is the number of vertices. Hence we need to check if the Prufer sequence consists of elements which are in the range [1, N].
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function that returns true if// given Prufer sequence is validbool isValidSeq(int a[], int n){ int nodes = n + 2; // Iterate in the Prufer sequence for (int i = 0; i < n; i++) { // If out of range if (a[i] < 1 || a[i] > nodes) return false; } return true;}// Driver codeint main(){ int a[] = { 4, 1, 3, 4 }; int n = sizeof(a) / sizeof(a[0]); if (isValidSeq(a, n)) cout << "Valid"; else cout << "Invalid"; return 0;} |
Java
// Java implementation of the approachimport java.io.*;class GFG {// Function that returns true if// given Prufer sequence is validstatic boolean isValidSeq(int []a, int n){ int nodes = n + 2; // Iterate in the Prufer sequence for (int i = 0; i < n; i++) { // If out of range if (a[i] < 1 || a[i] > nodes) return false; } return true;}// Driver codepublic static void main (String[] args) { int a[] = { 4, 1, 3, 4 }; int n = a.length; if (isValidSeq(a, n)) System.out.println( "Valid"); else System.out.print( "Invalid");}}// This code is contributed by anuj_67.. |
Python3
# Python3 implementation of the approach # Function that returns true if # given Prufer sequence is valid def isValidSeq(a, n) : nodes = n + 2; # Iterate in the Prufer sequence for i in range(n) : # If out of range if (a[i] < 1 or a[i] > nodes) : return False; return True; # Driver code if __name__ == "__main__" : a = [ 4, 1, 3, 4 ]; n = len(a); if (isValidSeq(a, n)) : print("Valid"); else : print("Invalid"); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System; class GFG {// Function that returns true if// given Prufer sequence is validstatic Boolean isValidSeq(int []a, int n){ int nodes = n + 2; // Iterate in the Prufer sequence for (int i = 0; i < n; i++) { // If out of range if (a[i] < 1 || a[i] > nodes) return false; } return true;}// Driver codepublic static void Main (String[] args) { int []a = { 4, 1, 3, 4 }; int n = a.Length; if (isValidSeq(a, n)) Console.WriteLine( "Valid"); else Console.WriteLine( "Invalid");}}// This code has been contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approach// Function that returns true if// given Prufer sequence is validfunction isValidSeq( a, n){ var nodes = n + 2; // Iterate in the Prufer sequence for (var i = 0; i < n; i++) { // If out of range if (a[i] < 1 || a[i] > nodes) return false; } return true;}// Driver codevar a = [ 4, 1, 3, 4 ];var n = a.length;if (isValidSeq(a, n)) document.write( "Valid" );else document.write( "Invalid");// This code is contributed by itsok.</script> |
Output
Valid
Time Complexity: O(n)
Auxiliary Space: O(1)
Approach 2: Using Maps:
This implementation uses a std::map<int, int> to count the frequency of each element in the sequence. It then iterates through the sequence and checks that each element is within the valid range (1 to n+2), occurs exactly once in the sequence, and corresponds to a leaf node in the tree (which is represented by the sequence itself). If all these conditions are met, the sequence is considered valid.
C++
#include <bits/stdc++.h>using namespace std;// Function that returns true if// given Prufer sequence is validbool isValidSeq(const vector<int>& seq){ int n = seq.size(); int nodes = n + 2; map<int, int> freq; // Count the frequency of each element for (int i = 0; i < n; i++) { freq[seq[i]]++; } // Iterate in the Prufer sequence for (int i = 0; i < n; i++) { // If out of range or not unique if (seq[i] < 1 || seq[i] > nodes || freq[seq[i]] != 1) return false; // Decrement the frequency of the corresponding leaf // node freq[nodes - i]--; } return true;}// Driver codeint main(){ vector<int> seq = { 4, 1, 3, 4 }; if (isValidSeq(seq)) cout << "Inalid"; else cout << "Valid"; return 0;} |
Java
/*package whatever //do not write package name here */import java.util.HashMap;import java.util.Map;import java.util.Scanner;public class Main { // Function that returns true if // given Prufer sequence is valid public static boolean isValidSeq(int[] seq) { int n = seq.length; int nodes = n + 2; Map<Integer, Integer> freq = new HashMap<Integer, Integer>(); // Count the frequency of each element for (int i = 0; i < n; i++) { int key = seq[i]; if (freq.containsKey(key)) { freq.put(key, freq.get(key) + 1); } else { freq.put(key, 1); } } // Iterate in the Prufer sequence for (int i = 0; i < n; i++) { // If out of range or not unique if (seq[i] < 1 || seq[i] > nodes || freq.get(seq[i]) != 1) { return false; } // Decrement the frequency of the corresponding // leaf node freq.put(nodes - i, freq.get(nodes - i) - 1); } return true; } // Driver code public static void main(String[] args) { int[] seq = { 4, 1, 3, 4 }; if (isValidSeq(seq)) System.out.println("Invalid"); else System.out.println("Valid"); }} |
Python3
def is_valid_seq(seq): n = len(seq) nodes = n + 2 freq = {} # Count the frequency of each element for i in range(n): key = seq[i] freq[key] = freq.get(key, 0) + 1 # Iterate in the Prufer sequence for i in range(n): # If out of range or not unique if seq[i] < 1 or seq[i] > nodes or freq[seq[i]] != 1: return False # Decrement the frequency of the corresponding leaf node freq[nodes - i] = freq.get(nodes - i, 0) - 1 return True# Driver codeseq = [4, 1, 3, 4]if is_valid_seq(seq): print("Inalid")else: print("Valid") |
Javascript
function isValidSeq(seq) { const n = seq.length; const nodes = n + 2; const freq = {}; // Count the frequency of each element for (let i = 0; i < n; i++) { const key = seq[i]; freq[key] = (freq[key] || 0) + 1; } // Iterate in the Prufer sequence for (let i = 0; i < n; i++) { // If out of range or not unique if (seq[i] < 1 || seq[i] > nodes || freq[seq[i]] !== 1) { return false; } // Decrement the frequency of the corresponding leaf node freq[nodes - i] = (freq[nodes - i] || 0) - 1; } return true;}// Driver codeconst seq = [4, 1, 3, 4];if (isValidSeq(seq)) { console.log("Invalid");} else { console.log("Valid");} |
C#
using System;using System.Collections.Generic;class Program { static bool IsValidSeq(List<int> seq) { int n = seq.Count; int nodes = n + 2; Dictionary<int, int> freq = new Dictionary<int, int>(); // Count the frequency of each element for (int i = 0; i < n; i++) { if (!freq.ContainsKey(seq[i])) { freq[seq[i]] = 0; } freq[seq[i]]++; } // Iterate in the Prufer sequence for (int i = 0; i < n; i++) { // If out of range or not unique if (seq[i] < 1 || seq[i] > nodes || freq[seq[i]] != 1) { return false; } // Decrement the frequency of the corresponding // leaf node freq[nodes - i]--; } return true; } static void Main(string[] args) { List<int> seq = new List<int>() { 4, 1, 3, 4 }; if (IsValidSeq(seq)) { Console.WriteLine("Invalid"); } else { Console.WriteLine("Valid"); } }} |
Output
Valid
Time Complexity: O(N)
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!
