Number Of Ways To Reconstruct A Tree - Video Solutions
1719. Number Of Ways To Reconstruct A Tree (Leetcode Hard)
Number Of Ways To Reconstruct A Tree - Video Solution
Watch 3 video solutions for Number Of Ways To Reconstruct A Tree, a hard level problem involving Tree, Graph. This walkthrough by Programming Live with Larry has 2,111 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 inpairsif and only ifxiis an ancestor ofyioryiis an ancestor ofxi. - 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:
0ifways == 01ifways == 12ifways > 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 <= 1051 <= xi < yi <= 500- The elements in
pairsare unique.
Approach Overview
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.
Complexity Analysis
| 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 |