# Number Of Ways To Reconstruct A Tree

Posted: 18 Mar, 2021
Difficulty: Hard

## 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.
``````
##### 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.
`````` Approach 1
• 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.