Number Of Ways To Reconstruct A Tree

Hard

#1575Time: 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.

Data structures

Tree Graph

Prompt

You are given an array pairs, where pairs[i] = [x_i, y_i], and:

There are no duplicates.
x_i < y_i

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 [x_i, y_i] exists in pairs if and only if x_i is an ancestor of y_i or y_i is an ancestor of x_i.
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:

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:

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 <= 10⁵
1 <= x_i< y_i <= 500
The elements in pairs are unique.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

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

Walkthrough

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.

1Map<Integer, List<Integer>> adj = new HashMap<>();2Map<Integer, Integer> degrees = new HashMap<>();3for (int[] pair : pairs) {4    adj.computeIfAbsent(pair[0], k -> new ArrayList<>()).add(pair[1]);5    adj.computeIfAbsent(pair[1], k -> new ArrayList<>()).add(pair[0]);6    degrees.put(pair[0], degrees.getOrDefault(pair[0], 0) + 1);7    degrees.put(pair[1], degrees.getOrDefault(pair[1], 0) + 1);8}

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:

1// For a node u and its parent p2for (int neighborOfU : adj.get(u)) {3    if (neighborOfU == p) continue;4    boolean found = false;5    for (int neighborOfP : adj.get(p)) {6        if (neighborOfP == neighborOfU) {7            found = true;8            break;9        }10    }11    if (!found) return 0; // Subset property violated12}

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.

Complexity

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.

Trade-offs

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.

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.

Algorithm

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.
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.
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.
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.
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.
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.
Return Result: If the process completes, return 1 if only one way was found, or 2 if ambiguities were detected.

Walkthrough

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.

1Map<Integer, Set<Integer>> adj = new HashMap<>();2Map<Integer, Integer> degrees = new HashMap<>();3for (int[] pair : pairs) {4    adj.computeIfAbsent(pair[0], k -> new HashSet<>()).add(pair[1]);5    adj.computeIfAbsent(pair[1], k -> new HashSet<>()).add(pair[0]);6    degrees.put(pair[0], degrees.getOrDefault(pair[0], 0) + 1);7    degrees.put(pair[1], degrees.getOrDefault(pair[1], 0) + 1);8}

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:

1// For a node u and its parent p2// Check if adj.get(u) is a subset of adj.get(p)3Set<Integer> neighborsOfP = adj.get(p);4for (int neighborOfU : adj.get(u)) {5    if (neighborOfU != p && !neighborsOfP.contains(neighborOfU)) {6        return 0; // Subset property violated7    }8}

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.

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int checkWays(int[][] pairs) {4    boolean[][] g = new boolean[510][510];5    List<Integer>[] v = new List[510];6    Arrays.setAll(v, k->new ArrayList<>());7    for (int[] p : pairs) {8      int x = p[0], y = p[1];9      g[x][y] = true;10      g[y][x] = true;11      v[x].add(y);12      v[y].add(x);13    }14    List<Integer> nodes = new ArrayList<>();15    for (int i = 0; i < 510; ++i) {16      if (!v[i].isEmpty()) {17        nodes.add(i);18        g[i][i] = true;19      }20    }21    nodes.sort(Comparator.comparingInt(a->v[a].size()));22    boolean equal = false;23    int root = 0;24    for (int i = 0; i < nodes.size(); ++i) {25      int x = nodes.get(i);26      int j = i + 1;27      for (; j < nodes.size() && !g[x][nodes.get(j)]; ++j)28        ;29      if (j < nodes.size()) {30        int y = nodes.get(j);31        if (v[x].size() == v[y].size()) {32          equal = true;33        }34        for (int z : v[x]) {35          if (!g[y][z]) {36            return 0;37          }38        }39      } else {40        ++root;41      }42    }43    if (root > 1) {44      return 0;45    }46    return equal ? 2 : 1;47  }48}

1class Solution {2public:3  int checkWays(vector<vector<int>> &pairs) {4    vector<vector<bool>> g(510, vector<bool>(510));5    vector<vector<int>> v(510);6    for (auto &p : pairs) {7      int x = p[0], y = p[1];8      g[x][y] = g[y][x] = 1;9      v[x].push_back(y);10      v[y].push_back(x);11    }12    vector<int> nodes;13    for (int i = 1; i <= 500; ++i) {14      if (v[i].size()) {15        nodes.push_back(i);16        g[i][i] = 1;17      }18    }19    sort(nodes.begin(), nodes.end(),20         [&](int x, int y) -> bool { return v[x].size() < v[y].size(); });21    bool equal = 0;22    int root = 0;23    for (int i = 0; i < nodes.size(); ++i) {24      int x = nodes[i];25      int j = i + 1;26      for (; j < nodes.size() && !g[x][nodes[j]]; ++j)27        ;28      if (j < nodes.size()) {29        int y = nodes[j];30        if (v[x].size() == v[y].size())31          equal = 1;32        for (int z : v[x])33          if (!g[y][z])34            return 0;35      } else36        ++root;37    }38    if (root > 1)39      return 0;40    if (equal)41      return 2;42    return 1;43  }44};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem