# Number Of Ways To Reconstruct A Tree

Posted: 18 Mar, 2021

Difficulty: Hard

#### 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.