Number Of Ways To Reconstruct A Tree

Hard
0/120
Average time to solve is 15m
3 upvotes
Asked in companies
UberMicrosoft

Problem statement

You are given an array ‘PAIRS’ consisting of ‘N’ pairs, where PAIRS[i] = [Xi, Yi] such that:

1. Xi < Yi.

2. There is no duplicate in the ‘PAIRS’ array.

You have to determine the number of ways to reconstruct a rooted tree that satisfies the following conditions:

1. The nodes of the tree must be present in the ‘PAIRS’ array.

2. A pair [Xi, Yi] exists in pairs if and only if Xi is an ancestor of Yi or Yi is an ancestor of Xi.

Two ways are considered to be different if there is at least one node that has different parents in both ways.

You should return: 
1. 0, if there is no way to reconstruct a tree.

2. 1, if there is exactly 1 way.

3. 2, if there is more than 1 way.

Note:

1. The tree does not necessarily have to be a binary tree.

2. A rooted tree is a tree that has a single root node, and all edges are oriented to be outgoing from the root.

3. An ancestor of a node is any node on the path from the root to that node. The root has no ancestors.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer ‘T’ denoting the number of test cases. 

The first line of each test case contains a single integer ‘N’, as described in the problem statement.

Then next ‘N’ lines contain two space-separated integers denoting the pair [Xi, Yi], as described in the problem statement.
Output Format: 
For each test case, print a single line containing either ‘0’,’1’, or ‘2’ depending on the number of ways to reconstruct the rooted tree.

The output of every test case will be printed in a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10 ^ 5
1 <= Xi < Yi <= 500

Where ‘T’ denotes the number of test cases and ‘N’ denotes the size of ‘PAIRS’.

Time Limit: 1 sec.
Sample Input 1:
1
4 
1 2
1 3
3 4
1 4
Sample Output 1:
2
Explanation for sample input 1:
There are 2 ways to reconstruct the rooted tree from the given input which are shown in the figure below.

altImage

Sample Input 2:
1
3 
1 2
2 3
3 4
Sample Output 2:
0
Explanation for sample input 2:
There is no way to reconstruct any rooted tree from the given input.
Hint

Reconstruct the tree from top to bottom.

Approaches (1)
Greedy Reconstruction
  • The main idea in this problem is that if we consider a node as a root then it must be paired with all of its descendants and its ancestors. So a parent's pairings will always contain a child's pairings.
  • So, we will create an adjacency list from the input pairs and we will reconstruct the tree from top to bottom.
  • Now if there are ‘M’ different nodes in the tree, then the root of the tree must have the degree = ‘M’ - 1. Therefore, if the node with the highest degree has its degree less than ‘M’ - 1 then the answer is 0 because there is no node that can be the root of the tree.
  • So, we will move from top to bottom by choosing the nodes with the highest degree first, and then we will choose a node with the least degree from the current node’s adjacency which is visited before to be the parent of the current node.
  • Now the parent’s adjacency must contain the current node’s adjacency, if this is not true the answer will be 0.
  • Now for more than 1 answer, if at any moment the current node and its parent has the same degree then there will be multiple trees possible as we can consider these nodes in any order.
  • So, if we can visit all nodes successfully then the answer is surely 1, but if we found a node such that it’s degree is equal to its parent’s degree, then there are multiple answers possible and hence the answer will be 2.
Time Complexity

O(N * log(N)), where ‘N’ is the size of the ‘PAIRS’ array.

 

If there are ‘N’ pairs in the ‘PAIRS’ array then the number of nodes in the tree will be of the order of O(N), Now we are processing order of O(N) nodes and for each node, we will be iterating in its adjacency list, therefore the over complexity will be of the order of O(N). But we will be using a priority queue to store the nodes and accessing a priority queue takes order of O(log(N)) time, therefore the overall time complexity will be of the order of O(N * log(N)).

Space Complexity

O(N), where ‘N’ is the size of the ‘PAIRS’ array.

 

Since we are creating an adjacency list from the input ‘PAIRS’ array and also we are storing the nodes in a priority queue, hence the space complexity will be of the order of O(N).

Code Solution
(100% EXP penalty)
Number Of Ways To Reconstruct A Tree
Full screen
Console