Possible edges of a tree for given diameter , height and vertices | C ++ program to construct tree for given count width and height . ; Function to construct the tree ; Special case when d == 2 , only one edge ; Tree is not possible ; Satisfy the height condition by add edges up to h ; Add d - h edges from 1 to satisfy diameter condition ; Remaining edges at vertex 1 or 2 ( d == h ) ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void constructTree ( int n , int d , int h ) { if ( d == 1 ) { if ( n == 2 && h == 1 ) { cout << "1 ▁ 2" << endl ; return ; } cout << " - 1" << endl ; return ; } if ( d > 2 * h ) { cout << " - 1" << endl ; return ; } for ( int i = 1 ; i <= h ; i ++ ) cout << i << " ▁ " << i + 1 << endl ; if ( d > h ) { cout << "1" << " ▁ " << h + 2 << endl ; for ( int i = h + 2 ; i <= d ; i ++ ) { cout << i << " ▁ " << i + 1 << endl ; } } for ( int i = d + 1 ; i < n ; i ++ ) { int k = 1 ; if ( d == h ) k = 2 ; cout << k << " ▁ " << i + 1 << endl ; } } int main ( ) { int n = 5 , d = 3 , h = 2 ; constructTree ( n , d , h ) ; return 0 ; }