Find a tree with the given values and print the edges of the tree. Print “-1”, if the tree is not possible.
Given three integers n, d and h.
n -> Number of vertices. [1, n] d -> Diameter of the tree (largest distance between two vertices). h -> Height of the tree (longest distance between vertex 1 and another vertex)
Examples :
Input : n = 5, d = 3, h = 2
Output : 1 2
2 3
1 4
1 5
Explanation :
We can see that the height of the tree is 2 (1 ->
2 --> 5) and diameter is 3 ( 3 -> 2 -> 1 -> 5).
So our conditions are satisfied.
Input : n = 8, d = 4, h = 2
Output : 1 2
2 3
1 4
4 5
1 6
1 7
1 8
Explanation :
- Observe that when d = 1, we cannot construct a tree (if tree has more than 2 vertices). Also when d > 2*h, we cannot construct a tree.
- As we know that height is the longest path from vertex 1 to another vertex. So build that path from vertex 1 by adding edges up to h. Now, if d > h, we should add another path to satisfy diameter from vertex 1, with a length of d – h.
- Our conditions for height and diameter are satisfied. But still some vertices may be left. Add the remaining vertices at any vertex other than the end points. This step will not alter our diameter and height. Choose vertex 1 to add the remaining vertices (you can choose any).
- But when d == h, choose vertex 2 to add the remaining vertices.
Implementation:
C++
// C++ program to construct tree for given count// width and height.#include <bits/stdc++.h>using namespace std;// Function to construct the treevoid constructTree(int n, int d, int h){ if (d == 1) { // Special case when d == 2, only one edge if (n == 2 && h == 1) { cout << "1 2" << endl; return; } cout << "-1" << endl; // Tree is not possible return; } if (d > 2 * h) { cout << "-1" << endl; return; } // Satisfy the height condition by add // edges up to h for (int i = 1; i <= h; i++) cout << i << " " << i + 1 << endl; if (d > h) { // Add d - h edges from 1 to // satisfy diameter condition cout << "1" << " " << h + 2 << endl; for (int i = h + 2; i <= d; i++) { cout << i << " " << i + 1 << endl; } } // Remaining edges at vertex 1 or 2(d == h) for (int i = d + 1; i < n; i++) { int k = 1; if (d == h) k = 2; cout << k << " " << i + 1 << endl; }}// Driver Codeint main(){ int n = 5, d = 3, h = 2; constructTree(n, d, h); return 0;} |
Java
// Java program to construct tree for given count // width and height. class GfG { // Function to construct the tree static void constructTree(int n, int d, int h) { if (d == 1) { // Special case when d == 2, only one edge if (n == 2 && h == 1) { System.out.println("1 2"); return; } System.out.println("-1"); // Tree is not possible return; } if (d > 2 * h) { System.out.println("-1"); return; } // Satisfy the height condition by add // edges up to h for (int i = 1; i <= h; i++) System.out.println(i + " " + (i + 1)); if (d > h) { // Add d - h edges from 1 to // satisfy diameter condition System.out.println("1" + " " + (h + 2)); for (int i = h + 2; i <= d; i++) { System.out.println(i + " " + (i + 1)); } } // Remaining edges at vertex 1 or 2(d == h) for (int i = d + 1; i < n; i++) { int k = 1; if (d == h) k = 2; System.out.println(k + " " + (i + 1)); } } // Driver Code public static void main(String[] args) { int n = 5, d = 3, h = 2; constructTree(n, d, h); } } |
Python3
# Python3 code to construct tree for given count# width and height.# Function to construct the treedef constructTree(n, d, h): if d == 1: # Special case when d == 2, only one edge if n == 2 and h == 1: print("1 2") return 0 print("-1") # Tree is not possible return 0 if d > 2 * h: print("-1") return 0 # Satisfy the height condition by add # edges up to h for i in range(1, h+1): print(i," " , i + 1) if d > h: # Add d - h edges from 1 to # satisfy diameter condition print(1," ", h + 2) for i in range(h+2, d+1): print(i, " " , i + 1) # Remaining edges at vertex 1 or 2(d == h) for i in range(d+1, n): k = 1 if d == h: k = 2 print(k ," " , i + 1)# Driver Coden = 5d = 3h = 2constructTree(n, d, h)# This code is contributed by "Sharad_Bhardwaj". |
C#
// C# program to construct tree for // given count width and height. using System; class GfG { // Function to construct the tree static void constructTree(int n, int d, int h) { if (d == 1) { // Special case when d == 2, // only one edge if (n == 2 && h == 1) { Console.WriteLine("1 2"); return; } // Tree is not possible Console.WriteLine("-1"); return; } if (d > 2 * h) { Console.WriteLine("-1"); return; } // Satisfy the height condition // by add edges up to h for (int i = 1; i <= h; i++) Console.WriteLine(i + " " + (i + 1)); if (d > h) { // Add d - h edges from 1 to // satisfy diameter condition Console.WriteLine("1" + " " + (h + 2)); for (int i = h + 2; i <= d; i++) { Console.WriteLine(i + " " + (i + 1)); } } // Remaining edges at vertex 1 or 2(d == h) for (int i = d + 1; i < n; i++) { int k = 1; if (d == h) k = 2; Console.WriteLine(k + " " + (i + 1)); } } // Driver Code public static void Main(String[] args) { int n = 5, d = 3, h = 2; constructTree(n, d, h); } } // This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to construct tree for// given count width and height.// Function to construct the treefunction constructTree(n, d, h) { if (d == 1) { // Special case when d == 2, // only one edge if (n == 2 && h == 1) { document.write("1 2", "<br>"); return; } // Tree is not possible document.write("-1", "<br>"); return; } if (d > 2 * h) { document.write("-1", "<br>"); return; } // Satisfy the height condition // by add edges up to h for(var i = 1; i <= h; i++) document.write(i + " " + (i + 1), "<br>"); if (d > h) { // Add d - h edges from 1 to // satisfy diameter condition document.write("1" + " " + (h + 2), "<br>"); for(var i = h + 2; i <= d; i++) { document.write(i + " " + (i + 1), "<br>"); } } // Remaining edges at vertex 1 or 2(d == h) for(var i = d + 1; i < n; i++) { var k = 1; if (d == h) k = 2; document.write(k + " " + (i + 1), "<br>"); } } // Driver Codevar n = 5, d = 3, h = 2; constructTree(n, d, h); // This code is contributed by bunnyram19</script> |
Output
1 2 2 3 1 4 1 5
Time Complexity: O(n), n is the number of vertices of the given tree.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
