# Number Of Ways To Reconstruct A Tree
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-ways-to-reconstruct-a-tree)
Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-to-reconstruct-a-tree
**Data structures:** Tree, Graph
---
## Problem
You are given an array `pairs`, where `pairs[i] = [xi, yi]`, and:

* There are no duplicates.
* `xi < yi`

Let `ways` be the number of rooted trees that satisfy the following conditions:

* The tree consists of nodes whose values appeared in `pairs`.
* A pair `[xi, yi]` exists in `pairs` **if and only if** `xi` is an ancestor of `yi` or `yi` is an ancestor of `xi`.
* **Note:** the tree does not have to be a binary tree.

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

Return:

* `0` if `ways == 0`
* `1` if `ways == 1`
* `2` if `ways > 1`

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

An **ancestor** of a node is any node on the path from the root to that node (excluding the node itself). The root has no ancestors.

**Example 1:**

![](https://assets.glich.co/dsa/number-of-ways-to-reconstruct-a-tree/image0.png) 

**Input:** pairs = [[1,2],[2,3]]
**Output:** 1
**Explanation:** There is exactly one valid rooted tree, which is shown in the above figure.

**Example 2:**

![](https://assets.glich.co/dsa/number-of-ways-to-reconstruct-a-tree/image1.png) 

**Input:** pairs = [[1,2],[2,3],[1,3]]
**Output:** 2
**Explanation:** There are multiple valid rooted trees. Three of them are shown in the above figures.

**Example 3:**

**Input:** pairs = [[1,2],[2,3],[2,4],[1,5]]
**Output:** 0
**Explanation:** There are no valid rooted trees.

**Constraints:**

* `1 <= pairs.length <= 105`
* `1 <= xi < yi <= 500`
* The elements in `pairs` are unique.

# Approaches
## Greedy Reconstruction with List-Based Adjacency
This approach reconstructs the tree by first establishing a hierarchy of nodes based on their degrees (number of relationships). The node with the highest degree is the most likely candidate for the root. By sorting nodes by degree, we can greedily assign parents to children. The main drawback of this specific implementation is the use of `List` for storing neighbors, which makes lookups and subset checks inefficient.
**Time:** O(N + M log M + M*N). Building the graph is O(N). Sorting nodes is O(M log M). The nested loops for parent finding and validation dominate. The outer loop runs M times. The inner loop for parent finding can run up to M times, with each neighbor check taking up to O(M) (degree can be up to M-1). The subset check also takes O(deg(u) * deg(p)), which can be O(M^2) in the worst case. This makes the total complexity significantly high. · **Space:** O(N + M), where N is the number of pairs and M is the number of unique nodes. This is for storing the adjacency lists, degrees, and other data structures.
**Pros:** The logic is sound and correctly identifies the necessary conditions for a valid tree reconstruction.; It correctly handles all cases, including impossible constructions and multiple valid ways.
**Cons:** The time complexity is high due to using lists for adjacency information. Checking for neighbors and verifying the subset property involves linear scans, making it inefficient for dense graphs or nodes with high degrees.
### Explanation
The core idea is that in a valid rooted tree, an ancestor node must be related to all nodes that its descendant is related to. This translates to a subset relationship between their neighbors in the graph formed by the `pairs`. We can formalize this by building the graph and then attempting to reconstruct the single-parent-for-each-node structure of a tree.

First, we process the `pairs` to build an adjacency list and a degree map. A `Map<Integer, List<Integer>>` can store the adjacency lists and a `Map<Integer, Integer>` for degrees.

```java
Map<Integer, List<Integer>> adj = new HashMap<>();
Map<Integer, Integer> degrees = new HashMap<>();
for (int[] pair : pairs) {
    adj.computeIfAbsent(pair[0], k -> new ArrayList<>()).add(pair[1]);
    adj.computeIfAbsent(pair[1], k -> new ArrayList<>()).add(pair[0]);
    degrees.put(pair[0], degrees.getOrDefault(pair[0], 0) + 1);
    degrees.put(pair[1], degrees.getOrDefault(pair[1], 0) + 1);
}
```

We then sort the nodes by degree. The node with the highest degree must be the root and have a degree of `n-1`, where `n` is the total number of nodes.

We iterate through the sorted nodes. For each node `u`, we find its parent `p` by searching backwards in the sorted list for a neighbor. Once a parent `p` is found, we must validate the subset property: `adj[u]` must be a subset of `adj[p]`. With lists, this check is slow:

```java
// For a node u and its parent p
for (int neighborOfU : adj.get(u)) {
    if (neighborOfU == p) continue;
    boolean found = false;
    for (int neighborOfP : adj.get(p)) {
        if (neighborOfP == neighborOfU) {
            found = true;
            break;
        }
    }
    if (!found) return 0; // Subset property violated
}
```

If `degrees.get(u) == degrees.get(p)`, we note that there are multiple ways. This check, combined with the subset validation, allows us to determine the final answer.
### Algorithm
1.  **Graph Representation**: Construct a graph where nodes are the numbers from `pairs`. An edge exists between two nodes if they appear in a pair. Use an adjacency list representation, where for each node, we store a list of its neighbors. Also, compute the degree of each node.
2.  **Identify Nodes and Root**: Find the total number of unique nodes, `n`. A valid tree must have a single root that is an ancestor to all other `n-1` nodes. This means the root must have a degree of `n-1`. If no such node exists, no tree is possible, so return `0`.
3.  **Sort Nodes**: Create a list of all nodes and sort them in descending order based on their degrees. This helps in establishing a hierarchy, as ancestors generally have more descendants and thus a higher degree.
4.  **Greedy Tree Construction**: Iterate through the sorted nodes, starting from the second node (the first is the root). For each node `u`, find its parent `p`.
    *   The parent `p` must be an ancestor of `u`, so it must be a neighbor of `u` in the graph (`p` is in `adj[u]`).
    *   The parent must also have a higher or equal degree, so it must appear before `u` in the sorted list.
    *   To find the *immediate* parent, we search for a neighbor of `u` that appears most recently in the sorted list (i.e., has the largest index smaller than `u`'s index). This is done by iterating backward from `u`'s position in the sorted list.
5.  **Validation during Construction**:
    *   For each node `u` and its found parent `p`, a critical property must hold: the set of `u`'s neighbors must be a subset of `p`'s neighbors (plus `p` itself). This is because any node related to `u` must also be related to its ancestor `p`. This check is performed by iterating through `u`'s neighbors and verifying their presence in `p`'s adjacency list. This is inefficient due to linear scans in lists.
    *   If the subset property is violated for any pair, no valid tree can be formed. Return `0`.
6.  **Check for Multiple Ways**: If a node `u` and its parent `p` have the same degree, it implies they are structurally symmetric with respect to their connections. This allows their roles as parent and child to be swapped, leading to a different valid tree. If such a case is found, it means there is more than one way to construct the tree. We can set a flag or a result variable to `2`.
7.  **Final Result**: If the entire process completes without returning `0`, it means at least one valid tree structure is found. Return `1` if no same-degree parent-child relationships were found, and `2` otherwise.

## Efficient Greedy Reconstruction with Hash Set Adjacency
This approach refines the previous one by using a more suitable data structure—a hash set—for the adjacency lists. This significantly speeds up the critical operations of checking for neighbors and verifying the subset property, reducing their complexity from linear to constant time on average. The overall algorithm remains a greedy construction based on node degrees, which correctly models the ancestor-descendant hierarchy.
**Time:** O(N + M^2). Building the graph is O(N). Sorting is O(M log M). The main loop runs M times. Inside, finding the parent takes O(M) in the worst case. The subset check takes O(degree of node). The sum of degrees is 2N. So the total time is dominated by the nested loops for parent finding, resulting in O(M^2), plus the initial setup and sum of degrees for checks, leading to O(N + M^2). · **Space:** O(N + M), where N is the number of pairs and M is the number of unique nodes. The space is used for the adjacency sets, degree map, and sorted node list.
**Pros:** Efficient implementation with O(1) average time complexity for neighbor lookups.; The overall time complexity of O(N + M^2) is efficient enough for the given constraints.; It's a complete and correct algorithm for this problem.
**Cons:** The time complexity is still polynomial, O(M^2), which might be slow for a much larger number of nodes (M), though it's perfectly fine for the given constraints.
### Explanation
The fundamental logic is the same as the less efficient approach, but performance is greatly improved by using hash-based data structures.

We start by building the graph using `Map<Integer, Set<Integer>>` for `adj`.

```java
Map<Integer, Set<Integer>> adj = new HashMap<>();
Map<Integer, Integer> degrees = new HashMap<>();
for (int[] pair : pairs) {
    adj.computeIfAbsent(pair[0], k -> new HashSet<>()).add(pair[1]);
    adj.computeIfAbsent(pair[1], k -> new HashSet<>()).add(pair[0]);
    degrees.put(pair[0], degrees.getOrDefault(pair[0], 0) + 1);
    degrees.put(pair[1], degrees.getOrDefault(pair[1], 0) + 1);
}
```

After sorting nodes by degree and identifying the root, we iterate through the sorted nodes `sortedNodes`. For each node `u = sortedNodes[i]`, we find its parent `p` by searching `sortedNodes[j]` for `j` from `i-1` down to `0`. The first `sortedNodes[j]` that is a neighbor of `u` is the parent `p`.

The crucial subset validation becomes much faster:

```java
// For a node u and its parent p
// Check if adj.get(u) is a subset of adj.get(p)
Set<Integer> neighborsOfP = adj.get(p);
for (int neighborOfU : adj.get(u)) {
    if (neighborOfU != p && !neighborsOfP.contains(neighborOfU)) {
        return 0; // Subset property violated
    }
}
```

This check is now O(degree of `u`) on average. The overall algorithm proceeds as described, checking for same-degree parent-child pairs to detect multiple ways. If `degrees.get(u) == degrees.get(p)`, we set `result = 2`. Finally, we return the calculated result.
### Algorithm
1.  **Graph Representation**: Construct a graph from the `pairs`. For efficient lookups, represent the adjacency list using a `Map<Integer, Set<Integer>>`. Also, compute the degree of each node and store it in a map.
2.  **Identify Nodes and Root**: Determine the set of unique nodes and its size, `n`. Find a node with degree `n-1` to be the root. If no such node exists, return `0`.
3.  **Sort Nodes by Degree**: Create a list of all nodes and sort it in descending order of their degrees. This establishes a potential hierarchy from root to leaves.
4.  **Greedy Parent Assignment**: Iterate through the sorted nodes from the second element to the end. For each node `u`:
    *   Find its parent `p` by iterating backward through the already processed (higher-degree) nodes in the sorted list. The first neighbor of `u` encountered is its parent `p`. This `p` is the 'closest' ancestor in the hierarchy.
    *   If no parent is found among the preceding nodes, the graph is not connected in a way that can form a tree, so return `0`.
5.  **Efficient On-the-fly Validation**:
    *   After finding a parent `p` for `u`, verify the subset property: every neighbor of `u` (except `p`) must also be a neighbor of `p`. With hash sets, this check is efficient (`adj.get(p).contains(neighbor)` is O(1) on average).
    *   If the check fails, return `0`.
6.  **Detect Multiple Reconstructions**: During validation, if a node `u` and its parent `p` have the same degree (`degrees.get(u) == degrees.get(p)`), it signifies a structural ambiguity. This means `u` and `p` could swap roles, leading to a different valid tree. In this case, we know there's more than one way, so we can set our result to `2`.
7.  **Return Result**: If the process completes, return `1` if only one way was found, or `2` if ambiguities were detected.

# Solutions
### Java

```java
class Solution {
public
  int checkWays(int[][] pairs) {
    boolean[][] g = new boolean[510][510];
    List<Integer>[] v = new List[510];
    Arrays.setAll(v, k->new ArrayList<>());
    for (int[] p : pairs) {
      int x = p[0], y = p[1];
      g[x][y] = true;
      g[y][x] = true;
      v[x].add(y);
      v[y].add(x);
    }
    List<Integer> nodes = new ArrayList<>();
    for (int i = 0; i < 510; ++i) {
      if (!v[i].isEmpty()) {
        nodes.add(i);
        g[i][i] = true;
      }
    }
    nodes.sort(Comparator.comparingInt(a->v[a].size()));
    boolean equal = false;
    int root = 0;
    for (int i = 0; i < nodes.size(); ++i) {
      int x = nodes.get(i);
      int j = i + 1;
      for (; j < nodes.size() && !g[x][nodes.get(j)]; ++j)
        ;
      if (j < nodes.size()) {
        int y = nodes.get(j);
        if (v[x].size() == v[y].size()) {
          equal = true;
        }
        for (int z : v[x]) {
          if (!g[y][z]) {
            return 0;
          }
        }
      } else {
        ++root;
      }
    }
    if (root > 1) {
      return 0;
    }
    return equal ? 2 : 1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int checkWays(vector<vector<int>> &pairs) {
    vector<vector<bool>> g(510, vector<bool>(510));
    vector<vector<int>> v(510);
    for (auto &p : pairs) {
      int x = p[0], y = p[1];
      g[x][y] = g[y][x] = 1;
      v[x].push_back(y);
      v[y].push_back(x);
    }
    vector<int> nodes;
    for (int i = 1; i <= 500; ++i) {
      if (v[i].size()) {
        nodes.push_back(i);
        g[i][i] = 1;
      }
    }
    sort(nodes.begin(), nodes.end(),
         [&](int x, int y) -> bool { return v[x].size() < v[y].size(); });
    bool equal = 0;
    int root = 0;
    for (int i = 0; i < nodes.size(); ++i) {
      int x = nodes[i];
      int j = i + 1;
      for (; j < nodes.size() && !g[x][nodes[j]]; ++j)
        ;
      if (j < nodes.size()) {
        int y = nodes[j];
        if (v[x].size() == v[y].size())
          equal = 1;
        for (int z : v[x])
          if (!g[y][z])
            return 0;
      } else
        ++root;
    }
    if (root > 1)
      return 0;
    if (equal)
      return 2;
    return 1;
  }
};

```

### Python

```python
class Solution:
    def checkWays(self, pairs: List[List[int]]) -> int: g = [[False] * 510 for _ in range(510)] v = defaultdict(list) for x, y in pairs: g[x][y] = g[y][x] = True v[x]. append(y) v[y]. append(x) nodes = [] for i in range(510): if v[i]: nodes . append(i) g[i][i] = True nodes . sort(key=lambda x: len(v[x])) equal = False root = 0 for i, x in enumerate(nodes): j = i + 1 while j < len(nodes) and not g[x][nodes[j]]: j += 1 if j < len(nodes): y = nodes[j] if len(v[x]) == len(v[y]): equal = True for z in v[x]: if not g[y][z]: return 0 else: root += 1 if root > 1: return 0 return 2 if equal else 1

```