LeetCode 1719 - Number Of Ways To Reconstruct A Tree
The problem provides an array of pairs, where each pair [xi, yi] indicates that xi is either an ancestor of yi or yi is an ancestor of xi in a rooted tree. The key challenge is to determine how many different rooted trees satisfy all given pairs.
Difficulty: 🔴 Hard
Topics: Array, Hash Table, Tree, Graph Theory, Simulation
Solution
Problem Understanding
The problem provides an array of pairs, where each pair [xi, yi] indicates that xi is either an ancestor of yi or yi is an ancestor of xi in a rooted tree. The key challenge is to determine how many different rooted trees satisfy all given pairs. We are not limited to binary trees; nodes can have any number of children. The output is 0 if no valid tree exists, 1 if exactly one tree exists, and 2 if multiple trees are possible.
The input guarantees no duplicate pairs and that for each pair xi < yi. The tree's nodes are only those that appear in the pairs. An important aspect is that a pair implies an ancestor-descendant relationship, but the direction is not given; we only know the two nodes are connected through the tree in some ancestor-descendant fashion.
The constraints suggest we need a solution efficient in both time and space. With up to 10^5 pairs and node values up to 500, the algorithm should avoid combinatorial tree enumeration and instead work with graph-like relationships using hash maps or adjacency sets.
Edge cases include: a tree that is linear (like a linked list), a tree that is star-shaped (all nodes connected to one root), disconnected nodes (invalid tree), and situations where multiple valid parents exist for a node (leading to multiple valid trees).
Approaches
The brute-force approach would attempt to generate all possible rooted trees from the node set and then validate each tree against the pairs. For each candidate tree, we would check all ancestor-descendant relationships. This approach is guaranteed to be correct but is computationally infeasible due to the combinatorial explosion of tree arrangements, especially given n up to 500.
The optimal approach relies on graph theory. Each node's adjacency set in the input represents potential parent-child relationships. The algorithm first identifies the node with the largest degree as the root candidate because the root should connect to all other nodes in some ancestor-descendant fashion. Then, for each node, we choose the parent as the adjacent node that has the smallest degree strictly greater than its own. If a node's adjacency is not a subset of its parent's adjacency, the tree is invalid. Multiple valid trees arise when a node has the same degree as its parent because the parent-child assignment could be swapped without violating ancestor constraints.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n!) | O(n^2) | Generate all trees and validate against pairs; infeasible for large n |
| Optimal | O(n^2) | O(n^2) | Uses adjacency sets and degrees to assign parents and detect multiple tree possibilities efficiently |
Algorithm Walkthrough
- Convert the list of
pairsinto a map from each node to its adjacency set. This captures all nodes directly connected to each node. - Identify the root. The root should connect to all other nodes, so it is the node with the largest adjacency set. If no node connects to all others, return
0. - For each node
v(excluding the root), identify a parent candidate. The parent must be an adjacent nodeuwhose adjacency set size is strictly greater thanv's and is the smallest such set. If no such parent exists, the tree is invalid. - Verify that each node's adjacency set is a subset of its parent's adjacency set. If any node violates this property, the tree is invalid, and we return
0. - Detect if multiple trees are possible. If a node has the same adjacency size as its parent, then swapping their roles preserves the ancestor-descendant relationships, so we set a flag indicating multiple valid trees.
- Return
2if multiple trees are possible, otherwise1.
Why it works: The adjacency sets encode ancestor-descendant relationships. By choosing the smallest parent whose adjacency set strictly contains the node's adjacency set, we ensure valid parent assignment. The root is the only node connected to all others. The property of subsets guarantees all ancestor pairs in pairs are satisfied.
Python Solution
from typing import List, Dict, Set
class Solution:
def checkWays(self, pairs: List[List[int]]) -> int:
from collections import defaultdict
# Step 1: Build adjacency sets
adj: Dict[int, Set[int]] = defaultdict(set)
nodes = set()
for u, v in pairs:
adj[u].add(v)
adj[v].add(u)
nodes.add(u)
nodes.add(v)
# Step 2: Find the root (node connected to all others)
n = len(nodes)
root = None
for node in nodes:
if len(adj[node]) == n - 1:
root = node
break
if root is None:
return 0
multiple = False
# Step 3: Assign parent for each node
for node in nodes:
if node == root:
continue
parent = None
for neighbor in adj[node]:
if len(adj[neighbor]) >= len(adj[node]):
if parent is None or len(adj[neighbor]) < len(adj[parent]):
parent = neighbor
if parent is None or not adj[node].issubset(adj[parent]):
return 0
if len(adj[parent]) == len(adj[node]):
multiple = True
return 2 if multiple else 1
Explanation: The adjacency sets are built to store direct connections. The root is identified by finding the node connected to all others. For each non-root node, we select the parent whose adjacency set strictly contains the node's adjacency set and is minimal in size. The subset check guarantees that all required ancestor-descendant relationships are satisfied. If a node has the same adjacency size as its parent, multiple trees are possible.
Go Solution
func checkWays(pairs [][]int) int {
adj := make(map[int]map[int]struct{})
nodes := make(map[int]struct{})
// Step 1: Build adjacency sets
for _, p := range pairs {
u, v := p[0], p[1]
if adj[u] == nil {
adj[u] = make(map[int]struct{})
}
if adj[v] == nil {
adj[v] = make(map[int]struct{})
}
adj[u][v] = struct{}{}
adj[v][u] = struct{}{}
nodes[u] = struct{}{}
nodes[v] = struct{}{}
}
n := len(nodes)
root := -1
for node := range nodes {
if len(adj[node]) == n-1 {
root = node
break
}
}
if root == -1 {
return 0
}
multiple := false
// Step 3: Assign parent for each node
for node := range nodes {
if node == root {
continue
}
var parent int = -1
for neighbor := range adj[node] {
if len(adj[neighbor]) >= len(adj[node]) {
if parent == -1 || len(adj[neighbor]) < len(adj[parent]) {
parent = neighbor
}
}
}
if parent == -1 {
return 0
}
for v := range adj[node] {
if _, ok := adj[parent][v]; !ok {
return 0
}
}
if len(adj[parent]) == len(adj[node]) {
multiple = true
}
}
if multiple {
return 2
}
return 1
}
Explanation: The Go version mirrors Python. Maps of integer sets represent adjacency. Root selection, parent assignment, subset checking, and multiple-tree detection follow the same logic. Go requires manual handling of sets using maps.
Worked Examples
Example 1: pairs = [[1,2],[2,3]]
| Node | Adjacency | Parent |
|---|---|---|
| 1 | {2} | 2? (2's size > 1) → yes |
| 2 | {1,3} | root candidate (connected to all?) → 2? → root = 2 |
| 3 | {2} | parent = 2 |
Only one valid tree exists.
Example 2: pairs = [[1,2],[2,3],[1,3]]
| Node | Adjacency | Parent |
|---|---|---|
| 1 | {2,3} | root (connected to all) → 1 |
| 2 | {1,3} | parent = 1 |
| 3 | {1,2} | parent = 1 or 2 → multiple valid trees |
Example 3: pairs = [[1,2],[2,3],[2,4],[1,5]]
Node 2 cannot find a valid parent covering its adjacency set entirely. Return 0.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n^2) | Each node checks all neighbors in its adjacency set; n ≤ 500 makes this feasible |
| Space | O(n^2) | Adjacency sets may store up to n-1 neighbors for each node |
Adjacency sets dominate both time and space due to subset checks. Each node has at most n-1 neighbors, and n ≤ 500 ensures O(n^2) is manageable.
Test Cases
# Example cases
assert Solution().checkWays([[1,2],[2,3]]) == 1 # Single valid tree
assert Solution().check