Taro Logo

Number Of Ways To Reconstruct A Tree

Hard
Asked by:
Profile picture
46 views
Topics:
GraphsTreesArrays

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

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 <= 105
  • 1 <= xi < yi <= 500
  • The elements in pairs are unique.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the format of the input? Is it a list of edge pairs (e.g., `[[u, v], [x, y]]`) representing the tree?
  2. Are the node values guaranteed to be unique integers? If so, what is the range of possible node values?
  3. If there are multiple possible trees that can be reconstructed from the given edge pairs, should I return `true` only if the reconstruction is unique, or `true` even if multiple reconstructions are possible?
  4. What should I return if no tree can be reconstructed from the given edge pairs?
  5. Will the input always represent an undirected graph, or could it be directed?

Brute Force Solution

Approach

We're given pairings of nodes that are supposed to be directly connected in a tree. The brute force method tries to construct every possible tree structure using these nodes, checking each one to see if it satisfies the given connectivity constraints.

Here's how the algorithm would work step-by-step:

  1. First, list out all the nodes that appear in the pairings.
  2. Next, generate every possible tree structure you can make with those nodes. This means trying every possible arrangement of nodes and connections.
  3. For each possible tree, check if all the pairings given to us are actually present in that tree. If a pairing is missing, that tree is no good.
  4. Also, check if the tree follows the rules of a tree: it should be connected, and there should be no loops or cycles.
  5. If a tree passes both checks, it's a valid reconstruction.
  6. Count how many valid reconstructions you found.
  7. Return the count of valid reconstructions. If there's only one, it's uniquely reconstructible, if there are zero then it's not reconstructible, and if there are more than one, it's ambiguously reconstructible.

Code Implementation

def number_of_ways_to_reconstruct_a_tree(pairs):
    nodes = set()
    for start_node, end_node in pairs:
        nodes.add(start_node)
        nodes.add(end_node)

    number_of_nodes = len(nodes)
    all_possible_trees = []

    def generate_trees(current_tree, remaining_nodes):
        if not remaining_nodes:
            all_possible_trees.append(current_tree)
            return

        node_to_add = remaining_nodes.pop()
        for i in range(len(current_tree) + 1):
            new_tree = current_tree[:]
            new_tree.insert(i, node_to_add)
            
            # Recursively generate trees by adding this node at every possible location
            generate_trees(new_tree, remaining_nodes.copy())

    generate_trees([], list(nodes))

    valid_tree_count = 0

    def is_valid_tree(tree, edge_pairs):
        # must have all nodes
        if len(tree) != number_of_nodes:
            return False

        adjacency_list = {node: [] for node in tree}

        # construct tree using provided pairs
        for start_node, end_node in edge_pairs:
            if start_node in tree and end_node in tree:
                start_index = tree.index(start_node)
                end_index = tree.index(end_node)

                adjacency_list[start_node].append(end_node)
                adjacency_list[end_node].append(start_node)

        edge_count = 0
        for node in adjacency_list:
            edge_count += len(adjacency_list[node])

        if edge_count != (number_of_nodes - 1) * 2:
            return False

        visited = set()
        
        # Check if the tree is connected
        def depth_first_search(node):
            visited.add(node)
            for neighbor in adjacency_list[node]:
                if neighbor not in visited:
                    depth_first_search(neighbor)

        if tree:
            depth_first_search(tree[0])
            if len(visited) != number_of_nodes:
                return False

        # Check for cycles, implicitly by checking edges and connectedness
        return True

    def all_pairs_exist(tree, pairs):
        # Use all nodes, not just tree nodes
        adjacency_list = {node: [] for node in nodes}
        for start_node, end_node in pairs:
            start_index = -1
            end_index = -1
            if start_node in tree:
                start_index = tree.index(start_node)
            if end_node in tree:
                end_index = tree.index(end_node)

            if start_index != -1 and end_index != -1:
              adjacency_list[start_node].append(end_node)
              adjacency_list[end_node].append(start_node)

        for start_node, end_node in pairs:
            
            if start_node in adjacency_list and end_node in adjacency_list[start_node]:
                continue
            else:
                return False

        return True

    for possible_tree in all_possible_trees:

        # We only proceed if all pairs are present in the possible tree
        if all_pairs_exist(possible_tree, pairs) : 
            # Check to ensure valid reconstruction, tree struct and no cycles
            if is_valid_tree(possible_tree, pairs):
                valid_tree_count += 1

    if valid_tree_count == 0:
        return 0
    elif valid_tree_count == 1:
        return 1
    else:
        return 2

Big(O) Analysis

Time Complexity
O((n^n) * (n^2) * n!) – The brute force approach involves generating all possible tree structures from n nodes, which is extremely expensive. Generating each tree structure can be loosely bounded by n^n, since each node can potentially connect to any other node. Verifying each tree requires checking if all provided pairings (let's say there are up to n^2 pairings) exist in the tree. Furthermore, we need to ensure it is a valid tree, which, without knowing the exact tree validation algorithm, could involve checking for cycles; a simple cycle detection would involve traversing a number of paths relative to the number of nodes, contributing a n! cost factor. Multiplying these components together yields a runtime of approximately O((n^n) * (n^2) * n!).
Space Complexity
O(2^N * N) – The algorithm generates every possible tree structure. Representing each tree requires storing N nodes and potentially N-1 edges. Since there can be a very large number of possible tree structures, potentially exponential in N, where N is the number of nodes, the space required to store all possible trees grows exponentially as O(2^N * N). Furthermore, checking each tree for connectivity and cycles might use additional space proportional to N in the worst case for data structures like visited sets or recursion stacks. Combining both considerations, the space complexity is bounded by O(2^N * N).

Optimal Solution

Approach

The problem asks us to determine if a unique tree can be reconstructed from a list of parent-child relationships. The core idea is to identify the root, build a potential tree, and then verify if this tree matches the provided relationships and if it is the only possible tree.

Here's how the algorithm would work step-by-step:

  1. First, find all the unique nodes that appear in the parent-child relationships. These will be the nodes of our potential tree.
  2. Then, for each node, determine all the nodes it's directly connected to (its neighbors) based on the given parent-child relationships. Store this neighbor information.
  3. Identify a potential root node. A good candidate for the root is a node that has a 'large' number of neighbors (specifically, find a node whose set of neighbors completely contains the neighbors of other nodes).
  4. Try to build a tree starting from this root. For each node, try to connect it to its neighbors, ensuring that no cycles are formed.
  5. Verify that the reconstructed tree's parent-child relationships exactly match the given input relationships. If they don't, it's impossible to reconstruct a tree.
  6. Check if the reconstructed tree is unique. This can be determined by finding other valid root nodes and seeing if they could also generate valid trees matching the parent-child relationships. If more than one root is possible, it means the tree is not uniquely reconstructable.

Code Implementation

def number_of_ways_to_reconstruct_tree(pairs):
    all_nodes = set()
    neighbor_map = {}

    for parent, child in pairs:
        all_nodes.add(parent)
        all_nodes.add(child)

        if parent not in neighbor_map:
            neighbor_map[parent] = set()
        if child not in neighbor_map:
            neighbor_map[child] = set()

        neighbor_map[parent].add(child)
        neighbor_map[child].add(parent)

    def build_tree(root_node):
        tree = {}
        visited = {root_node}
        stack = [(root_node, None)]

        while stack:
            node, parent = stack.pop()
            tree[node] = parent

            for neighbor in sorted(neighbor_map[node], key=lambda x: len(neighbor_map[x]), reverse=True):
                if neighbor != parent:
                    if neighbor in visited:
                        # Cycle detected
                        return None
                    visited.add(neighbor)
                    stack.append((neighbor, node))
        if len(visited) != len(all_nodes):
            return None
        return tree

    def verify_tree(tree):
        for parent, child in pairs:
            node1, node2 = parent, child
            found = False
            
            current_node = node2
            while current_node is not None:
                if current_node == node1:
                    found = True
                    break
                current_node = tree.get(current_node)

            if not found:
                current_node = node1
                found = False
                while current_node is not None:
                    if current_node == node2:
                        found = True
                        break
                    current_node = tree.get(current_node)

                if not found:
                    return False

        return True

    possible_roots = []
    for node in all_nodes:
        is_potential_root = True
        for other_node in all_nodes:
            if node != other_node and neighbor_map[node].issuperset(neighbor_map[other_node]):
                continue
            elif node != other_node and not neighbor_map[other_node].issubset(neighbor_map[node]):
                is_potential_root = False
                break
        if is_potential_root:
            possible_roots.append(node)

    if not possible_roots:
        # No possible tree
        return 0

    valid_trees = 0
    for root in possible_roots:
        potential_tree = build_tree(root)
        if potential_tree and verify_tree(potential_tree):
            valid_trees += 1

    # Check for single vs multiple reconstructions
    if valid_trees == 0:
        return 0
    elif valid_trees == 1:
        return 1
    else:
        # Not uniquely reconstructable
        return 2

Big(O) Analysis

Time Complexity
O(n^2) – Finding all unique nodes and creating the adjacency lists (neighbors) iterates through the input `pairs` list, taking O(n) time where n represents the number of pairs. Identifying a potential root requires comparing sets of neighbors, which involves nested loops to check subset relationships among all nodes' neighbors, resulting in O(n^2) time, where n is the number of nodes (which is bounded by the number of pairs). Building and verifying the tree, and checking uniqueness, also involves traversing the neighbor lists and sets derived from the input pairs; however, the root-finding step dominates the complexity. Therefore, the overall time complexity is dominated by the root identification step and set comparisons, which is approximately n * n operations in the worst case, where n is the number of nodes, simplifying to O(n^2).
Space Complexity
O(N^2) – The algorithm uses auxiliary space to store the unique nodes, their neighbors, and potentially the reconstructed tree structure. The neighbor information for each node could potentially store all other nodes as neighbors, leading to an adjacency list representation that could take O(N^2) space in the worst-case scenario where N is the number of nodes. Furthermore, verifying the reconstructed tree might require creating another adjacency list-like structure, adding to the space complexity. Therefore, the dominant factor in space complexity is the storage of node neighbors, resulting in O(N^2) space.

Edge Cases

Null or empty list of edges
How to Handle:
Return 1 if empty (a single node is possible), or 0 if null (invalid input).
A single node (no edges)
How to Handle:
Return 1, as a single node is a valid tree.
Disconnected graph (multiple components)
How to Handle:
Return 0, as a tree must be a single connected component.
Graph contains a cycle
How to Handle:
Return 0, as a tree cannot contain cycles.
Input represents a star graph
How to Handle:
Check to make sure only one root is valid.
Complete graph, fully connected
How to Handle:
The number of possible trees may be high; verify efficient processing.
Duplicate edges in the input list
How to Handle:
Treat multiple identical edges as a single edge; handle during graph construction
The implied tree has a node count larger than the number of input nodes
How to Handle:
Return 0, as the edge list implies a number of distinct nodes that is inconsistent.