You are given an array pairs, where pairs[i] = [xi, yi], and:
xi < yiLet ways be the number of rooted trees that satisfy the following conditions:
pairs.[xi, yi] exists in pairs if and only if xi is an ancestor of yi or yi is an ancestor of xi.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 == 01 if ways == 12 if ways > 1A 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 <= 1051 <= xi < yi <= 500pairs are unique.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:
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:
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 2The 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:
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| Case | How to Handle |
|---|---|
| Null or empty list of edges | Return 1 if empty (a single node is possible), or 0 if null (invalid input). |
| A single node (no edges) | Return 1, as a single node is a valid tree. |
| Disconnected graph (multiple components) | Return 0, as a tree must be a single connected component. |
| Graph contains a cycle | Return 0, as a tree cannot contain cycles. |
| Input represents a star graph | Check to make sure only one root is valid. |
| Complete graph, fully connected | The number of possible trees may be high; verify efficient processing. |
| Duplicate edges in the input list | 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 | Return 0, as the edge list implies a number of distinct nodes that is inconsistent. |