We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number Of Ways To Reconstruct A Tree

Number: 1820

Difficulty: Hard

Paid? No

Companies: Uber

Problem Description

Given a list of pairs where each pair [x, y] (with x < y) implies that in the target rooted tree one of x or y is an ancestor of the other, determine how many valid rooted trees can be constructed such that:

  • The set of nodes is exactly the set of all numbers appearing in pairs.
  • For every pair [x, y], x is an ancestor of y or vice versa, and vice versa—if there is an ancestral relationship between two nodes then the pair must have appeared. Return:
  • 0 if no valid tree exists,
  • 1 if there is exactly one valid tree,
  • 2 if there are multiple valid trees (i.e. more than one).

Key Insights

  • Build an undirected graph (adjacency list) from the pairs. The graph encodes required ancestral relationships.
  • The “root” candidate must be connected to every other node (its degree should be n-1).
  • For every non-root node, choose as its parent a neighbor that has a strictly higher degree (i.e. is “more connected”) than the current node.
  • The candidate parent’s neighbors must contain the non-root node’s neighbors because all nodes connected to the child must be present in the parent’s subtree.
  • If a candidate non-root node has more than one potential valid parent (for example, when degrees are equal), then multiple valid trees are possible.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case, where n is the number of unique nodes (up to 500) because for each node we might check inclusion over sets of neighbors. Space Complexity: O(n + m) where n is the number of nodes and m is the number of pairs, for building the graph and storing neighbor sets.

Solution

We first construct a neighbor set for each node from the given pairs. Then we identify the candidate for the root: the node whose neighbor set includes all other nodes. If no such node exists, no valid tree exists.

Next, we sort the non-root nodes based on their degree (the size of their neighbor set) in descending order. For each non-root node, we must assign a parent from among its neighbors that has a higher degree than itself. The candidate parent should have a neighbor set that is a superset of the current node’s neighbors. If such a candidate does not exist, the reconstruction is impossible.

While choosing the parent, if the degree of the candidate parent is exactly the same as the current node then there exist multiple ways to choose the parent; we then mark the answer as 2. If all assignments are uniquely determined, the answer remains 1. Otherwise, we output 0 if any check fails.

Data structures used:

  • A hash map (or dictionary) to store neighbor sets for each node.
  • Sorting a list of nodes based on degree. The algorithm relies on set inclusion checks to verify the ancestral relationship requirements.

Code Solutions

# Python solution with line-by-line comments
from collections import defaultdict

def checkWays(pairs):
    # Build neighbor sets for all nodes
    neighbors = defaultdict(set)
    for u, v in pairs:
        neighbors[u].add(v)
        neighbors[v].add(u)
    
    # Get the unique nodes
    nodes = list(neighbors.keys())
    n = len(nodes)
    
    # Identify the candidate root.
    # The root must be connected to all other nodes (degree equals n-1)
    root = None
    for node in nodes:
        if len(neighbors[node]) == n - 1:
            root = node
            break
    if not root:
        return 0  # No valid root candidate
    
    # Sort the nodes in descending order by degree.
    # The root will be processed first and skipped in the next iteration.
    nodes.sort(key=lambda x: len(neighbors[x]), reverse=True)

    # Initialize answer as unique tree until proven otherwise.
    ways = 1
    # Dictionary to store each node's degree for quick access
    degree = {node: len(neighbors[node]) for node in nodes}
    
    # For each node (except the root), determine its parent.
    for node in nodes:
        if node == root:
            continue  # Skip the root candidate
        # Initialize parent candidate with an impossible high value for degree
        parentCandidate = None
        for neighbor in neighbors[node]:
            if degree[neighbor] > degree[node]:
                # Pick the candidate with the smallest degree among those greater than current degree.
                if parentCandidate is None or degree[neighbor] < degree[parentCandidate]:
                    parentCandidate = neighbor
        
        # If no valid parent candidate is found, tree reconstruction is impossible.
        if parentCandidate is None:
            return 0
        
        # Verify that the candidate parent's neighbor set contains the current node's neighbor set.
        # Exclude the current node itself since it might appear in parent's neighbors.
        # We check set(neighbors[node]) ⊆ set(neighbors[parentCandidate])
        if not neighbors[node].issubset(neighbors[parentCandidate]):
            return 0
        
        # If the parent's degree equals the child's degree, it indicates ambiguity.
        if degree[parentCandidate] == degree[node]:
            ways = 2
            
    return ways

# Example usage:
# print(checkWays([[1,2],[2,3],[1,3]]))  # Expected output: 2
← Back to All Questions