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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number Of Ways To Reconstruct A Tree

Difficulty: Hard

Problem Description

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 in pairs if and only if xi is an ancestor of yi or yi is an ancestor of xi.
  • 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:

  • 0 if ways == 0
  • 1 if ways == 1
  • 2 if ways > 1

Key Insights

  • The problem requires constructing a rooted tree from given pairs.
  • Each pair indicates a parent-child relationship.
  • The pairs can help deduce the structure of the tree and validate its uniqueness.
  • A node can have multiple candidates for children, leading to multiple valid trees.
  • If there's a cycle or inconsistency in the parent-child relationships, the answer is 0.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can use a graph-based approach:

  1. Graph Representation: Use an adjacency list to represent the relationships defined by pairs.
  2. Degree Counting: Count the number of parents for each node. A valid tree should have exactly one root (node with 0 parents) and all other nodes should have exactly one parent.
  3. DFS or BFS: Traverse the graph to ensure no cycles exist and to count valid configurations of trees.
  4. Determine Ways: Based on the traversal, determine how many valid trees can be formed. If multiple children are available for a node, multiply the number of ways.

Code Solutions

def countWays(pairs):
    from collections import defaultdict, Counter
    
    graph = defaultdict(list)
    indegree = Counter()
    
    for x, y in pairs:
        graph[x].append(y)
        indegree[y] += 1
        if x not in indegree:
            indegree[x] = 0
    
    roots = [node for node in indegree if indegree[node] == 0]
    
    if len(roots) != 1:
        return 0
    
    def dfs(node):
        if node not in graph:
            return 1
        total_ways = 1
        children = graph[node]
        for child in children:
            total_ways *= dfs(child)
        return total_ways
    
    ways = dfs(roots[0])
    return 1 if ways == 1 else 2 if ways > 1 else 0

# Example usage
print(countWays([[1, 2], [2, 3]]))  # Output: 1
print(countWays([[1, 2], [2, 3], [1, 3]]))  # Output: 2
print(countWays([[1, 2], [2, 3], [2, 4], [1, 5]]))  # Output: 0
← Back to All Questions