You are given an array pairs, where pairs[i] = [xi, yi], and:
xi < yiLet ways be the number of rooted trees that satisfy the following conditions:
pairs.[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.
Return:
0 if ways == 01 if ways == 12 if ways > 1A 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 <= 1051 <= xi < yi <= 500pairs are unique.Problem Overview: You receive a list of node pairs that represent ancestor relationships in an unknown tree. The task is to determine whether these pairs can reconstruct a valid tree and count how many distinct trees satisfy all relationships. The answer is 0 if reconstruction is impossible, 1 if the tree is uniquely determined, and 2 if multiple valid trees exist.
Approach 1: Union-Find with Degree Counting (O(n^2) time, O(n^2) space)
Treat every pair as an undirected connection and build an adjacency structure. The key observation: in a valid reconstruction, the root must be connected to every other node, meaning its degree equals n - 1. After identifying the root, process nodes by descending degree and assign each node a parent among its neighbors with a higher or equal degree. Union-Find helps maintain connectivity while validating that ancestor relationships don't contradict earlier assignments. If two candidate parents share identical degrees and neighbor sets, multiple reconstructions exist, so return 2. This approach works well when reasoning about connectivity and component merging using Union-Find.
Approach 2: Graph Construction Verification (O(n^2) time, O(n^2) space)
Build a graph where each node stores all neighbors from the pair list. Select the root as the node connected to all others. For every remaining node, search among its neighbors for the parent candidate with the smallest degree that is still larger than or equal to the node's degree. Verify that the node's neighbor set (excluding the parent) is contained within the parent's neighbor set. This ensures the parent truly dominates the subtree in the ancestor hierarchy. If any neighbor constraint fails, the reconstruction is impossible. If a node and its parent have the same degree, there are multiple valid parent assignments, so the answer becomes 2. This solution directly validates structural constraints of tree reconstruction using graph adjacency relationships.
Recommended for interviews: The graph construction verification approach is typically expected. It clearly models the ancestor relationships and shows you understand how node degrees reveal parent-child hierarchy. A brute reasoning approach helps explain the constraints, but implementing the adjacency validation with degree ordering demonstrates stronger algorithmic skill.
This approach uses a Union-Find (Disjoint Set Union) data structure to track connected components and determine ancestries recursively. Additionally, maintain a degree count for each node to find potential roots and ensure the tree is connected.
If there's a node with a degree equal to the number of nodes minus one, it's the root. If more than one such node exists, there are multiple possible trees.
This code implements a union-find structure to connect nodes based on the pairs given. It finds the number of possible ways to create a tree from these pairs by analyzing the degree of each node. If there's one node with a degree equal to the total number of nodes minus one, it can potentially be the root.
Python
JavaScript
Time Complexity: O(N) where N is the number of nodes, because each of the operations in the union-find has nearly constant time complexity.
Space Complexity: O(N) due to storing nodes, their degrees, and adjacency list.
This method involves constructing the graph represented by the pairs, maintaining an adjacency list, and validating the graph's tree structure potential. Specifically, ensure the graph has a single connected component and checks if the degree conditions for trees are met.
This Java implementation builds adjacency lists and checks degree conditions to identify potential root nodes. If an appropriate root is found, a DFS determines whether a single connected component includes all nodes, confirming a valid tree structure.
Time Complexity: O(n + m) where n is the number of nodes and m is the number of pairs.
Space Complexity: O(n + m) due to adjacency and degree maps' storage requirements.
| Approach | Complexity |
|---|---|
| Union-Find with Degree Counting | Time Complexity: O(N) where N is the number of nodes, because each of the operations in the union-find has nearly constant time complexity. |
| Graph Construction Verification | Time Complexity: O(n + m) where n is the number of nodes and m is the number of pairs. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find with Degree Counting | O(n^2) | O(n^2) | Useful when modeling pair connectivity and verifying ancestor consistency with disjoint sets |
| Graph Construction Verification | O(n^2) | O(n^2) | General case; preferred interview solution for validating parent-child hierarchy |
1719. Number Of Ways To Reconstruct A Tree (Leetcode Hard) • Programming Live with Larry • 2,066 views views
Watch 2 more video solutions →Practice Number Of Ways To Reconstruct A Tree with our built-in code editor and test cases.
Practice on FleetCode