Make a tree with n vertices , d diameter and at most vertex degree k | Function to Make a tree with n vertices , d as it 's diameter and degree of each vertex is at most k ; If diameter > n - 1 impossible to build tree ; To store the degree of each vertex ; To store the edge between vertices ; To store maximum distance among all the paths from a vertex ; Make diameter of tree equals to d ; Add an edge between them ; Store maximum distance of each vertex from other vertices ; For next ( n - d - 1 ) edges ; If the vertex already has the degree k ; If not possible ; Increase the degree of vertices ; Add an edge between them ; Store the maximum distance of this vertex from other vertices ; Print all the edges of the built tree ; Driver code
function Make_tree ( n , d , k ) { if ( d > n - 1 ) { document . write ( " " ) ; return ; } let deg = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) { deg [ i ] = 0 ; } let ans = [ ] ; let q = new Set ( ) ; for ( let i = 0 ; i < d ; ++ i ) { ++ deg [ i ] ; ++ deg [ i + 1 ] ; if ( deg [ i ] > k deg [ i + 1 ] > k ) { document . write ( " " ) ; return ; } ans . push ( [ i , i + 1 ] ) ; } for ( let i = 1 ; i < d ; ++ i ) q . add ( [ Math . max ( i , d - i ) , i ] ) ; for ( let i = d + 1 ; i < n ; ++ i ) { let arr = Array . from ( q ) ; while ( q . size != 0 && deg [ arr [ 0 ] [ 1 ] ] == k ) q . delete ( arr [ 0 ] ) ; if ( q . size == 0 arr [ 0 ] [ 0 ] == d ) { document . write ( " " ) return ; } ++ deg [ i ] ; ++ deg [ arr [ 0 ] [ 1 ] ] ; ans . push ( [ i , arr [ 0 ] [ 1 ] ] ) ; q . add ( [ arr [ 0 ] [ 0 ] + 1 , i ] ) ; } for ( let i = 0 ; i < n - 1 ; ++ i ) document . write ( ( ans [ i ] [ 0 ] + 1 ) + " " + ( ans [ i ] [ 1 ] + 1 ) + " " ) ; } let n = 6 , d = 3 , k = 4 ; Make_tree ( n , d , k ) ;