Construct an N | Java program to implement the above approach ; Keep track of visited nodes ; Function to construct a tree such that there are no two adjacent nodes with the same weight ; If minimum and maximum elements are equal , i . e . array contains one distinct element ; Tree cannot be constructed ; Otherwise ; Tree can be constructed ; Choose weights [ 0 ] as root ; First Node is visited ; Traverse the array ; Otherwise , make an edge ; Mark this node as visited ; Find a weight not same as the root & make edges with that node ; Join non - roots with remaining nodes ; Check if current node ' s ▁ weight ▁ ▁ is ▁ same ▁ as ▁ root ▁ node ' s weight and if it is not visited or not ; Driver Code ; Function Call
import java . lang . * ; import java . io . * ; import java . util . * ; class GFG { static int N = 100000 + 5 ; static int visited [ ] = new int [ N ] ; static void construct_tree ( int weights [ ] , int n ) { int minimum = Arrays . stream ( weights ) . min ( ) . getAsInt ( ) ; int maximum = Arrays . stream ( weights ) . max ( ) . getAsInt ( ) ; if ( minimum == maximum ) { System . out . println ( " No " ) ; return ; } else { System . out . println ( " Yes " ) ; } int root = weights [ 0 ] ; visited [ 1 ] = 1 ; for ( int i = 0 ; i < n ; i ++ ) { if ( weights [ i ] != root && visited [ i + 1 ] == 0 ) { System . out . println ( 1 + " ▁ " + ( i + 1 ) + " ▁ " ) ; visited [ i + 1 ] = 1 ; } } int notroot = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( weights [ i ] != root ) { notroot = i + 1 ; break ; } } for ( int i = 0 ; i < n ; i ++ ) { if ( weights [ i ] == root && visited [ i + 1 ] == 0 ) { System . out . println ( notroot + " ▁ " + ( i + 1 ) ) ; visited [ i + 1 ] = 1 ; } } } public static void main ( String [ ] args ) { int weights [ ] = { 1 , 2 , 1 , 2 , 5 } ; int N = weights . length ; construct_tree ( weights , N ) ; } }