Check if the given Prufer sequence is valid or not
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 valid bool 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 code int 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 approach import java.io.*; class GFG { // Function that returns true if // given Prufer sequence is valid static 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 code public 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 approach using System; class GFG { // Function that returns true if // given Prufer sequence is valid static 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 code public 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 valid function 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 code var 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> |
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 valid bool 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 code int 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 code seq = [ 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 code const 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" ); } } } |
Valid
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us