Given an array weights[] consisting of N positive integer, where weights[i] denotes the weight of ith node, the task is to construct an N-ary tree such that no two directly connected nodes have same weight. If it is possible to make such a tree, then print “Yes” along with their edges. Otherwise, print “No”.
Examples:
Input: weights[] = {1 2 1 2 5}
Output:
Yes
1 2
1 4
1 5
2 3
Explanation:
Index: 1 2 3 4 5
Weight : 1 2 1 2 5
The constructed Tree is shown in the following diagram:
Input: weights[] = {1 1 1}
Output: No
Explanation: Since all weights are already same, no such tree can be constructed.
Approach: The idea to solve this problem is to first check if all nodes are assigned with same weight or not. If found to be true, then required tree cannot be constructed. Otherwise, such a tree can be constructed. Therefore traverse the array weights[] and check if all values are the same or not. If found to be true, then print “No”. Otherwise, print “Yes” and construct a tree using the following steps:
- Take any node and make it the root node.
- Now, connect all other nodes with weights not equal to that of the root to the root node. Now the remaining nodes are the nodes that have a value equal to the root node.
- Choose any child node of the root node and connect all remaining nodes to them. Therefore, there exists no direct edge between nodes of same weight.
- To check which nodes have not been included yet, keep track of visited nodes using an auxiliary array visited[]. If a node is visited, join a node with it, but do not join the visited node with another node as joining an unvisited node with a visited node is possible, but not vice versa.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; // Keep track of visited nodes int visited[N]; // Function to construct a tree such // that there are no two adjacent // nodes with the same weight void construct_tree( int weights[], int n) { int minimum = *min_element(weights, weights + n); int maximum = *max_element(weights, weights + n); // If minimum and maximum // elements are equal, i.e. // array contains one distinct element if (minimum == maximum) { // Tree cannot be constructed cout << "No" ; return ; } // Otherwise else { // Tree can be constructed cout << "Yes" << endl; } // Find the edges below // Choose weights[0] as root int root = weights[0]; // First Node is visited visited[1] = 1; // Traverse the array for ( int i = 0; i < n; i++) { // If current element has the // same weight as root and if // the node is visited, then // do not make an edge // Otherwise, make an edge if (weights[i] != root && visited[i + 1] == 0) { cout << 1 << " " << i + 1 << " " << endl; // Mark this node as visited visited[i + 1] = 1; } } // Find a weight not same as the // root & make edges with that node int notroot = 0; for ( int i = 0; i < n; i++) { if (weights[i] != root) { notroot = i + 1; break ; } } // Join non-roots with remaining nodes for ( int i = 0; i < n; i++) { // Check if current node's weight // is same as root node's weight // and if it is not visited or not if (weights[i] == root && visited[i + 1] == 0) { cout << notroot << " " << i + 1 << endl; visited[i + 1] = 1; } } } // Driver Code int main() { int weights[] = { 1, 2, 1, 2, 5 }; int N = sizeof (weights) / sizeof (weights[0]); // Function Call construct_tree(weights, N); } |
Java
// Java program to implement // the above approach import java.lang.*; import java.io.*; import java.util.*; class GFG{ static int N = 100000 + 5 ; // Keep track of visited nodes static int visited[] = new int [N]; // Function to construct a tree such // that there are no two adjacent // nodes with the same weight static void construct_tree( int weights[], int n) { int minimum = Arrays.stream(weights).min().getAsInt(); int maximum = Arrays.stream(weights).max().getAsInt(); // If minimum and maximum // elements are equal, i.e. // array contains one distinct element if (minimum == maximum) { // Tree cannot be constructed System.out.println( "No" ); return ; } // Otherwise else { // Tree can be constructed System.out.println( "Yes" ); } // Find the edges below // Choose weights[0] as root int root = weights[ 0 ]; // First Node is visited visited[ 1 ] = 1 ; // Traverse the array for ( int i = 0 ; i < n; i++) { // If current element has the // same weight as root and if // the node is visited, then // do not make an edge // Otherwise, make an edge if (weights[i] != root && visited[i + 1 ] == 0 ) { System.out.println( 1 + " " + (i + 1 ) + " " ); // Mark this node as visited visited[i + 1 ] = 1 ; } } // Find a weight not same as the // root & make edges with that node int notroot = 0 ; for ( int i = 0 ; i < n; i++) { if (weights[i] != root) { notroot = i + 1 ; break ; } } // Join non-roots with remaining nodes for ( int i = 0 ; i < n; i++) { // Check if current node's weight // is same as root node's weight // and if it is not visited or not if (weights[i] == root && visited[i + 1 ] == 0 ) { System.out.println(notroot + " " + (i + 1 )); visited[i + 1 ] = 1 ; } } } // Driver Code public static void main(String[] args) { int weights[] = { 1 , 2 , 1 , 2 , 5 }; int N = weights.length; // Function Call construct_tree(weights, N); } } // This code is contributed by sanjoy_62 |
Python3
# Python3 program to implement # the above approach N = 10 * * 5 + 5 #Keep track of visited nodes visited = [ 0 ] * N #Function to construct a tree such #that there are no two adjacent #nodes with the same weight def construct_tree(weights, n): minimum = min (weights) maximum = max (weights) #If minimum and maximum #elements are equal, i.e. #array contains one distinct element if (minimum = = maximum): #Tree cannot be constructed print ( "No" ) return #Otherwise else : print ( "Yes" ) #Find the edges below #Choose weights[0] as root root = weights[ 0 ] #First Node is visited visited[ 1 ] = 1 #Traverse the array for i in range (n): #If current element has the #same weight as root and if #the node is visited, then #do not make an edge #Otherwise, make an edge if (weights[i] ! = root and visited[i + 1 ] = = 0 ): print ( 1 ,i + 1 ) #Mark this node as visited visited[i + 1 ] = 1 #Find a weight not same as the #root & make edges with that node notroot = 0 for i in range (n): if (weights[i] ! = root): notroot = i + 1 break #Join non-roots with remaining nodes for i in range (n): #Check if current node's weight #is same as root node's weight #and if it is not visited or not if (weights[i] = = root and visited[i + 1 ] = = 0 ): print (notroot,i + 1 ) visited[i + 1 ] = 1 #Driver Code if __name__ = = '__main__' : weights = [ 1 , 2 , 1 , 2 , 5 ] N = len (weights) #Function Call construct_tree(weights, N) |
C#
// C# program to implement // the above approach using System; using System.Linq; class GFG{ static int N = 100000 + 5; // Keep track of visited nodes static int [] visited = new int [N]; // Function to construct a tree such // that there are no two adjacent // nodes with the same weight static void construct_tree( int [] weights, int n) { int minimum = weights.Min(); int maximum = weights.Max(); // If minimum and maximum // elements are equal, i.e. // array contains one distinct element if (minimum == maximum) { // Tree cannot be constructed Console.WriteLine( "No" ); return ; } // Otherwise else { // Tree can be constructed Console.WriteLine( "Yes" ); } // Find the edges below // Choose weights[0] as root int root = weights[0]; // First Node is visited visited[1] = 1; // Traverse the array for ( int i = 0; i < n; i++) { // If current element has the // same weight as root and if // the node is visited, then // do not make an edge // Otherwise, make an edge if (weights[i] != root && visited[i + 1] == 0) { Console.WriteLine(1 + " " + (i + 1) + " " ); // Mark this node as visited visited[i + 1] = 1; } } // Find a weight not same as the // root & make edges with that node int notroot = 0; for ( int i = 0; i < n; i++) { if (weights[i] != root) { notroot = i + 1; break ; } } // Join non-roots with remaining nodes for ( int i = 0; i < n; i++) { // Check if current node's weight // is same as root node's weight // and if it is not visited or not if (weights[i] == root && visited[i + 1] == 0) { Console.WriteLine(notroot + " " + (i + 1)); visited[i + 1] = 1; } } } // Driver Code public static void Main() { int [] weights = { 1, 2, 1, 2, 5 }; int N = weights.Length; // Function Call construct_tree(weights, N); } } // This code is contributed by code_hunt. |
Javascript
<script> // Javascript program to implement // the above approach let N = 100000 + 5; // Keep track of visited nodes let visited = new Array(N); visited.fill(0); // Function to construct a tree such // that there are no two adjacent // nodes with the same weight function construct_tree(weights, n) { let minimum = Number.MAX_VALUE; let maximum = Number.MIN_VALUE; for (let i = 0; i < weights.length; i++) { minimum = Math.min(minimum, weights[i]); maximum = Math.max(maximum, weights[i]); } // If minimum and maximum // elements are equal, i.e. // array contains one distinct element if (minimum == maximum) { // Tree cannot be constructed document.write( "No" ); return ; } // Otherwise else { // Tree can be constructed document.write( "Yes" + "</br>" ); } // Find the edges below // Choose weights[0] as root let root = weights[0]; // First Node is visited visited[1] = 1; // Traverse the array for (let i = 0; i < n; i++) { // If current element has the // same weight as root and if // the node is visited, then // do not make an edge // Otherwise, make an edge if (weights[i] != root && visited[i + 1] == 0) { document.write(1 + " " + (i + 1) + "</br>" ); // Mark this node as visited visited[i + 1] = 1; } } // Find a weight not same as the // root & make edges with that node let notroot = 0; for (let i = 0; i < n; i++) { if (weights[i] != root) { notroot = i + 1; break ; } } // Join non-roots with remaining nodes for (let i = 0; i < n; i++) { // Check if current node's weight // is same as root node's weight // and if it is not visited or not if (weights[i] == root && visited[i + 1] == 0) { document.write(notroot + " " + (i + 1) + "</br>" ); visited[i + 1] = 1; } } } // Driver code let weights = [ 1, 2, 1, 2, 5 ]; let n = weights.length; // Function Call construct_tree(weights, n); // This code is contributed by divyeshrabadiya07 </script> |
Yes 1 2 1 4 1 5 2 3
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!