1719. Number Of Ways To Reconstruct A Tree - Leetcode Solution

Problem Description

Given a list of pairs pairs where each pair [xi, yi] indicates that node xi and node yi are directly connected in a tree, determine how many different valid trees can be reconstructed from these pairs.

If there is no valid tree that can be reconstructed, return 0.
If there is exactly one valid tree, return 1.
If there are multiple valid trees, return 2.

A valid tree must satisfy the following:

Each node is connected and there are no cycles.
The set of pairs exactly describes the parent-child relationships in the tree (not a forest, not a graph with cycles).

Constraints:

Each element in pairs is a list of two integers.
All nodes are labeled with positive integers.
Do not reuse elements or create extra connections.

Thought Process

At first glance, the problem looks like a standard "reconstruct a tree from edges" task. However, the twist is that we must determine how many distinct valid trees can be reconstructed, not just whether one exists.

The brute-force approach would be to try all possible tree structures that can be built from the given pairs and count them. However, this is inefficient because the number of possible trees grows very quickly with the number of nodes.

To optimize, we need to leverage properties specific to trees:

Every pair must be part of a single connected acyclic component.
Each node except the root has exactly one parent.
We can use the degree (number of connections) of each node to infer possible parent-child relationships.

This leads us to look for the node with the highest degree (likely the root) and to check for ambiguous cases (where multiple arrangements are possible).

Solution Approach

The solution involves the following steps:

Build the Adjacency List: For each pair, add both connections to an adjacency list. This helps us quickly look up the neighbors of any node.
Sort Nodes by Degree: Since the root will have the largest degree (connected to all others in its subtree), we sort nodes by their number of neighbors.
Determine Parent-Child Relationships: For each node, its parent must have a degree greater than or equal to its own. For each node, we look for the smallest neighbor with a higher or equal degree to assign as its parent.
Validate Tree Structure: For each node, ensure that its set of neighbors (excluding its parent) is a subset of its parent's neighbors. If not, the structure is invalid.
Count Ambiguities: If a node and its parent have the same degree, there is ambiguity in which is the parent and which is the child. If any such ambiguity exists, there are multiple valid trees.
Return the Result:
- Return 0 if invalid.
- Return 2 if ambiguous.
- Return 1 if exactly one valid tree exists.

We use hash maps for O(1) neighbor lookups and degree calculations.

Example Walkthrough

Input: pairs = [[1,2],[2,3]]

Build adjacency list:
- 1: [2]
- 2: [1,3]
- 3: [2]
Sort nodes by degree:
- 2 (degree 2), 1 and 3 (degree 1)
Assign parents:
- Node 1: parent is 2 (degree 2 > 1)
- Node 3: parent is 2 (degree 2 > 1)
- Node 2: no parent (root candidate)
Validate structure:
- Neighbors of 1 (excluding parent 2): {} is subset of 2's neighbors [1,3]
- Neighbors of 3 (excluding parent 2): {} is subset of 2's neighbors [1,3]
Check ambiguities:
- Degrees are not equal for any parent-child pair, so only one valid tree.
Return: 1

Time and Space Complexity

Brute-force approach:

Time: Exponential, as it tries all possible tree structures.
Space: Exponential, to store possible trees.

Optimized approach:

Time: O(N^2), where N is the number of unique nodes. This is due to set operations for neighbor checks and sorting by degree.
Space: O(N^2), for the adjacency list and neighbor sets.

The algorithm is efficient for reasonable input sizes.

Summary

This problem tests your understanding of tree structure and reconstruction from pairwise relationships. The key insight is to use degrees to infer parent-child relationships and to check for ambiguous cases where multiple reconstructions are possible. By leveraging adjacency lists and careful validation, we can efficiently determine whether the tree is unique, ambiguous, or impossible to reconstruct.

Code Implementation

from collections import defaultdict

class Solution:
    def checkWays(self, pairs):
        adj = defaultdict(set)
        for x, y in pairs:
            adj[x].add(y)
            adj[y].add(x)

        nodes = list(adj.keys())
        # Sort nodes by degree (descending), root should have highest degree
        nodes.sort(key=lambda x: -len(adj[x]))
        res = 1

        for i, node in enumerate(nodes):
            par = -1
            par_deg = float('inf')
            # Look for parent: neighbor with degree >= node's degree
            for nei in adj[node]:
                if len(adj[nei]) >= len(adj[node]) and len(adj[nei]) < par_deg:
                    par = nei
                    par_deg = len(adj[nei])
            if par == -1:
                if i == 0:
                    continue  # root
                else:
                    return 0
            # The node's neighbors (except parent) must be subset of parent's neighbors
            if not adj[node] - {par} <= adj[par]:
                return 0
            # If degrees are equal, ambiguity exists
            if len(adj[node]) == len(adj[par]):
                res = 2
        return res

#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Solution {
public:
    int checkWays(vector<vector<int>>& pairs) {
        unordered_map<int, unordered_set<int>> adj;
        for (auto& p : pairs) {
            adj[p[0]].insert(p[1]);
            adj[p[1]].insert(p[0]);
        }
        vector<int> nodes;
        for (auto& kv : adj) nodes.push_back(kv.first);
        sort(nodes.begin(), nodes.end(), [&adj](int a, int b) {
            return adj[a].size() > adj[b].size();
        });
        int res = 1;
        for (int i = 0; i < nodes.size(); ++i) {
            int node = nodes[i];
            int par = -1, par_deg = 1e9;
            for (int nei : adj[node]) {
                if (adj[nei].size() >= adj[node].size() && adj[nei].size() < par_deg) {
                    par = nei;
                    par_deg = adj[nei].size();
                }
            }
            if (par == -1) {
                if (i == 0) continue; // root
                else return 0;
            }
            // Check if all neighbors of node except parent are in parent's neighbors
            for (int nei : adj[node]) {
                if (nei == par) continue;
                if (!adj[par].count(nei)) return 0;
            }
            if (adj[node].size() == adj[par].size()) res = 2;
        }
        return res;
    }
};

import java.util.*;

class Solution {
    public int checkWays(int[][] pairs) {
        Map<Integer, Set<Integer>> adj = new HashMap<>();
        for (int[] p : pairs) {
            adj.computeIfAbsent(p[0], k -> new HashSet<>()).add(p[1]);
            adj.computeIfAbsent(p[1], k -> new HashSet<>()).add(p[0]);
        }
        List<Integer> nodes = new ArrayList<>(adj.keySet());
        nodes.sort((a, b) -> adj.get(b).size() - adj.get(a).size());
        int res = 1;
        for (int i = 0; i < nodes.size(); ++i) {
            int node = nodes.get(i);
            int par = -1, parDeg = Integer.MAX_VALUE;
            for (int nei : adj.get(node)) {
                if (adj.get(nei).size() >= adj.get(node).size() && adj.get(nei).size() < parDeg) {
                    par = nei;
                    parDeg = adj.get(nei).size();
                }
            }
            if (par == -1) {
                if (i == 0) continue;
                else return 0;
            }
            for (int nei : adj.get(node)) {
                if (nei == par) continue;
                if (!adj.get(par).contains(nei)) return 0;
            }
            if (adj.get(node).size() == adj.get(par).size()) res = 2;
        }
        return res;
    }
}

var checkWays = function(pairs) {
    let adj = {};
    for (let [x, y] of pairs) {
        if (!adj[x]) adj[x] = new Set();
        if (!adj[y]) adj[y] = new Set();
        adj[x].add(y);
        adj[y].add(x);
    }
    let nodes = Object.keys(adj).map(Number);
    nodes.sort((a, b) => adj[b].size - adj[a].size);
    let res = 1;
    for (let i = 0; i < nodes.length; ++i) {
        let node = nodes[i];
        let par = -1, parDeg = Infinity;
        for (let nei of adj[node]) {
            if (adj[nei].size >= adj[node].size && adj[nei].size < parDeg) {
                par = nei;
                parDeg = adj[nei].size;
            }
        }
        if (par == -1) {
            if (i == 0) continue;
            else return 0;
        }
        for (let nei of adj[node]) {
            if (nei == par) continue;
            if (!adj[par].has(nei)) return 0;
        }
        if (adj[node].size === adj[par].size) res = 2;
    }
    return res;
};

AlgoMap.io

Want Help Cracking FAANG?