1719. Number Of Ways To Reconstruct A Tree


Problem Description

You are given an array called pairs where each element in this array is a pair of integers [xi, yi], indicating a relationship between two elements with no duplicates and where xi is always less than yi. The goal is to determine the number of unique rooted trees that can be constructed where:

  1. The trees are formed by nodes whose values come from the pairs.
  2. For each pair [xi, yi], either xi is an ancestor of yi, or yi is an ancestor of xi and this relationship is captured if and only if the pair exists in pairs.
  3. The tree is a rooted tree, meaning it has a single specified root node, and edges are directed away from this root.
  4. A rooted tree does not necessarily have to be a binary tree.

The term ancestor refers to any node along the path from the root to that node, excluding the node itself, and the root node is the only node without ancestors.

The problem asks to determine the number of possible unique rooted trees, returning:

  • 0 if no such trees can be constructed,
  • 1 if exactly one unique tree can be constructed,
  • 2 if more than one unique tree can be constructed.

Intuition

To approach this problem, we focus on the properties of a rooted tree, particularly, the fact that ancestors have a specific relationship in the tree and that the root node would typically be the node with the highest number of connections, reflecting its position at the top of the tree with no ancestors.

We can start by considering the following points:

  1. Searching for the root node of these trees: The node with the most connections is likely the root, as in a tree each child has exactly one parent, and the root will be the only node without a parent.
  2. Once we find a potential root, we can check if the relationships described by pairs adhere to the constraints of being ancestor-descendant relationships.
  3. If there are multiple possible roots, or if at any point the ancestor-descendant relationship does not hold for any pair, we can be sure that no such tree exists.
  4. If we can construct exactly one tree, our answer is 1; if we find that there's more than one way to arrange nodes to create valid trees, the answer is 2.

From this intuition, the solution could be approached as follows:

  • We'll want to efficiently check the relationships between pairs of nodes. A graph data structure can help us keep track of all pairings.
  • We sort the nodes based on the number of connections they have, in descending order, to quickly identify potential root nodes (nodes with the most connections).
  • We iterate over this sorted list, verifying connections, and ensuring that our ancestor-descendant relationships hold.
  • We need to watch for special cases, such as when two nodes have the same number of connections -- this indicates that we may have multiple valid solutions.
  • If we find multiple root nodes or violations of the ancestor-descendant rule, we immediately know there are zero ways to construct the tree.
  • If we can construct the tree without finding such conflicting situations, we then check whether we've encountered a situation indicating multiple solutions.

The solution code implements these ideas by using a graph represented by a matrix (g) to track the pairings and a dictionary (v) to quickly list the connections each node has. It then works through the logical process described above to reach the final answer.

Learn more about Tree and Graph patterns.

Solution Approach

The solution provided uses graph theory principles to create a graph to represent the possible rooted trees. The following steps are executed in the solution:

Step 1: Data Structures

  • A 2D list (g[]) of size 510x510 is used to represent the adjacency matrix of the graph, where the indices are node values and a True value at g[x][y] represents an edge between nodes x and y. Initially, it's filled with False, and the indices are up to 510 as an upper limit on the number of different nodes.
  • A dictionary (v) where the key is a node and the value is a list of other nodes connected to it.

Step 2: Building the Graph

  • Iteration over pairs [[xi, yi]]. For each pair, both g[xi][yi] and g[yi][xi] are set to True, as the graph is undirected. Also, xi and yi are appended to each other's connection list in v.

Step 3: Sorting Nodes and Marking Self Connections

  • A list of nodes nodes is created from keys in v (which guarantees no duplicates as v is a dictionary).
  • Each node is marked connected to itself: g[i][i] is set to True.
  • nodes is sorted based on the length of their connections list (v[x]) to prioritize nodes with more connections, as they are more likely to be ancestors.

Step 4: Finding a Root and Checking Ancestor-Descendant Relations

  • The solution starts to iterate over nodes, for each x in nodes, it searches for a y that has a direct connection to x (g[x][y] is True).
  • If a node with an equal number of connections is found (len(v[x]) == len(v[y])), equal is set to True, indicating a potential for multiple solutions.
  • For every node z connected to x, it checks if z is also connected to y (g[y][z]). If not, it returns 0, because y must be the ancestor of all x's connections.
  • If no connected y is found after the iteration, root is incremented, identifying a potential root.

Step 5: Determining the Final Output

  • If more than one root is found (root > 1), the function returns 0 as it is not possible to have more than one root in a rooted tree.
  • If the process completes without inconsistencies or extra roots, but equal was flagged as True at any point, then there are multiple ways to arrange the tree, and 2 is returned.
  • Otherwise, if exactly one valid tree configuration is found, 1 is returned.

The algorithm constructs potential trees by establishing the root nodes based on their connection count while also ensuring that each node's ancestor-descendant constraints are respected. It uses a graph represented by an adjacency matrix to check the connections between nodes and employs a sorting strategy to quickly identify potential roots and validate the trees' structures.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we have the following pairs of relationships represented as an array pairs: [[1,2], [1,3], [3,4]].

Step 1: Data Structures

We initialize an adjacency matrix g[][] with a size of 510x510. All values are initially set to False. Also, we prepare a dictionary v to maintain a list of connections for each node.

Step 2: Building the Graph

For each pair:

  • [[1,2]]: We set g[1][2] and g[2][1] to True and put 2 in the list of v[1] and 1 in the list of v[2].
  • [[1,3]]: We set g[1][3] and g[3][1] to True and append 3 to the list of v[1] and 1 to the list of v[3].
  • [[3,4]]: We set g[3][4] and g[4][3] to True and append 4 to the list of v[3] and 3 to the list of v[4].

Following these steps, we have connections represented as:

  • v[1] contains [2, 3]
  • v[2] contains [1]
  • v[3] contains [1, 4]
  • v[4] contains [3]

Step 3: Sorting Nodes and Marking Self Connections

We create a list nodes with unique values of nodes [1, 2, 3, 4]. Self-connections are marked by setting g[i][i] to True for all i in nodes. The list nodes is then sorted by the length of their connection list in v, resulting in [1, 3, 2, 4].

Step 4: Finding a Root and Checking Ancestor-Descendant Relations

We start iterating over the sorted nodes:

  • Looking at node 1, it is connected to nodes 2 and 3. There is no other node with the same length of connectivity so we proceed.
  • Next, we consider node 3, which has two connections, to nodes 1 and 4. We see that node 3 is a descendant of node 1, so the relationship holds.
  • We continue for the rest, but since the length of connectivity is decreasing, no further checks for the root are needed.

No multiple roots or violations of ancestor-descendant relationships are found.

Step 5: Determining the Final Output

Since we found exactly one root (node 1) and there is no indication of potential multiple solutions (no equal flagged), the algorithm returns 1 - meaning exactly one unique tree can be constructed with node 1 as its root, node 2 and node 3 as its children, and node 4 as a child of node 3.

This walkthrough demonstrates how the algorithm efficiently constructs a graph, identifies a potential root, and validates the constraints to determine the number of unique rooted trees that can be constructed from the given pairs.

Solution Implementation

1from collections import defaultdict
2
3class Solution:
4    def checkWays(self, pairs: List[List[int]]) -> int:
5        # Create a graph as a 2D adjacency matrix initialized with False
6        graph = [[False] * 510 for _ in range(510)]
7      
8        # Vertex map to keep track of adjacent vertices
9        adjacency_map = defaultdict(list)
10      
11        # Fill the graph and the adjacency map based on the input pairs
12        for node1, node2 in pairs:
13            graph[node1][node2] = graph[node2][node1] = True
14            adjacency_map[node1].append(node2)
15            adjacency_map[node2].append(node1)
16          
17        # Collect valid nodes and sort based on the number of adjacent vertices
18        nodes = [node for node in range(510) if adjacency_map[node]]
19        nodes.sort(key=lambda node: len(adjacency_map[node]))
20      
21        # Flag to check if there's a pair of nodes with equal number of adjacent nodes
22        has_equal_adjacency_nodes = False
23      
24        # Counter for root nodes
25        root_counter = 0
26      
27        # Iterate through the nodes to validate the tree structure
28        for i, node in enumerate(nodes):
29            next_node_index = i + 1
30            # Find the next node which shares an edge with the current node
31            while next_node_index < len(nodes) and not graph[node][nodes[next_node_index]]:
32                next_node_index += 1
33              
34            if next_node_index < len(nodes):
35                potential_parent = nodes[next_node_index]
36                # Check if the current node has the same number of adjacent nodes as a possible parent node
37                if len(adjacency_map[node]) == len(adjacency_map[potential_parent]):
38                    has_equal_adjacency_nodes = True
39                # Check if the possible parent node is connected to all the adjacent nodes of the current node
40                for adjacent in adjacency_map[node]:
41                    if not graph[potential_parent][adjacent]:
42                        # The structure cannot form a tree if the connection is missing
43                        return 0
44            else:
45                # Increment root counter if no parent node is found
46                root_counter += 1
47      
48        # If there are more than one root, the structure cannot form a tree
49        if root_counter > 1:
50            return 0
51      
52        # Return 2 if there's at least one pair of nodes with the same number of adjacent nodes, else return 1
53        return 2 if has_equal_adjacency_nodes else 1
54
1class Solution {
2    public int checkWays(int[][] pairs) {
3        // Adjacency matrix to represent the graph's connections
4        boolean[][] adjacencyMatrix = new boolean[510][510];
5      
6        // Adjacency lists to track connections for each node
7        List<Integer>[] adjacencyLists = new List[510];
8        Arrays.setAll(adjacencyLists, k -> new ArrayList<>());
9      
10        // Fill the adjacency matrix and lists based on given pairs
11        for (int[] pair : pairs) {
12            int node1 = pair[0], node2 = pair[1];
13            adjacencyMatrix[node1][node2] = true;
14            adjacencyMatrix[node2][node1] = true;
15            adjacencyLists[node1].add(node2);
16            adjacencyLists[node2].add(node1);
17        }
18      
19        // Collect all nodes that are part of the graph
20        List<Integer> nodes = new ArrayList<>();
21        for (int i = 0; i < 510; ++i) {
22            if (!adjacencyLists[i].isEmpty()) {
23                nodes.add(i);
24                adjacencyMatrix[i][i] = true;
25            }
26        }
27      
28        // Sort nodes based on the number of connections they have
29        nodes.sort(Comparator.comparingInt(node -> adjacencyLists[node].size()));
30        boolean isParentChildCountEqual = false;
31        int rootCount = 0;
32      
33        // Loop to validate if the graph can represent a BST
34        for (int i = 0; i < nodes.size(); ++i) {
35            int currentNode = nodes.get(i);
36            int j = i + 1;
37          
38            // Find a node which is connected to the current node
39            while (j < nodes.size() && !adjacencyMatrix[currentNode][nodes.get(j)]) {
40                ++j;
41            }
42          
43            if (j < nodes.size()) {
44                int parentNode = nodes.get(j);
45                // Check if the parent node and the current node have the same number of children
46                if (adjacencyLists[currentNode].size() == adjacencyLists[parentNode].size()) {
47                    isParentChildCountEqual = true;
48                }
49                // Validate that all connections of the current node are also connections of the parent node.
50                for (int childNode : adjacencyLists[currentNode]) {
51                    if (!adjacencyMatrix[parentNode][childNode]) {
52                        return 0; // Return 0 if the tree structure cannot be formed
53                    }
54                }
55            } else {
56                ++rootCount; // Count potential root nodes
57            }
58        }
59      
60        // There can only be one root in a BST
61        if (rootCount > 1) {
62            return 0;
63        }
64        // Return 2 if there's a possibility of multiple BSTs being formed, otherwise 1
65        return isParentChildCountEqual ? 2 : 1;
66    }
67}
68
1class Solution {
2public:
3    int checkWays(vector<vector<int>>& pairs) {
4        // Define a matrix to represent a graph and an adjacency list.
5        vector<vector<bool>> graph(510, vector<bool>(510));
6        vector<vector<int>> adjacencyList(510);
7      
8        // Initialize the graph with the given pairs.
9        for (auto& pair : pairs) {
10            int node1 = pair[0], node2 = pair[1];
11            graph[node1][node2] = graph[node2][node1] = true;
12            adjacencyList[node1].push_back(node2);
13            adjacencyList[node2].push_back(node1);
14        }
15      
16        // Create and populate a list of nodes present in the graph.
17        vector<int> nodesList;
18        for (int node = 1; node <= 500; ++node) {
19            if (adjacencyList[node].size()) {
20                nodesList.push_back(node);
21                graph[node][node] = true; // A node is always connected to itself.
22            }
23        }
24      
25        // Sort the nodes based on the degree (number of neighbors), in ascending order.
26        sort(nodesList.begin(), nodesList.end(), [&](int nodeX, int nodeY) -> bool {
27            return adjacencyList[nodeX].size() < adjacencyList[nodeY].size();
28        });
29
30        // Will be used to detect if there are two nodes with the same degree.
31        bool hasEqualDegreeNodes = false;
32        // Counter to check how many possible root nodes we have.
33        int rootCount = 0;
34      
35        // Iterate through each node to check if the graph can form a tree.
36        for (int i = 0; i < nodesList.size(); ++i) {
37            int currentNode = nodesList[i];
38            int nextNodeIndex = i + 1;
39          
40            // Find the next node in the sorted list that is connected to the current node.
41            while (nextNodeIndex < nodesList.size() && !graph[currentNode][nodesList[nextNodeIndex]]) {
42                ++nextNodeIndex;
43            }
44          
45            // If a connected node is found, validate further.
46            if (nextNodeIndex < nodesList.size()) {
47                int nextNode = nodesList[nextNodeIndex];
48                // Check if the current and next nodes have the same degree.
49                if (adjacencyList[currentNode].size() == adjacencyList[nextNode].size()) {
50                    hasEqualDegreeNodes = true;
51                }
52              
53                // Make sure all neighbors of the currentNode are connected to nextNode.
54                for (int neighbor : adjacencyList[currentNode])
55                    if (!graph[nextNode][neighbor])
56                        return 0; // Return 0 if the neighbor is not connected to the next node.
57              
58            } else {
59                // If no connected node is found, increment root count as it might be a root.
60                ++rootCount;
61            }
62        }
63
64        // If there is more than one root, it can’t form a tree.
65        if (rootCount > 1) return 0;
66
67        // If there are nodes with equal degrees, there are two ways to arrange the tree.
68        if (hasEqualDegreeNodes) return 2;
69
70        // If the execution reaches here, there is exactly one way to arrange the tree.
71        return 1;
72    }
73};
74
1// Define a matrix to represent a graph and an adjacency list.
2const graph: boolean[][] = Array.from({ length: 510 }, () => Array(510).fill(false));
3const adjacencyList: number[][] = Array.from({ length: 510 }, () => []);
4
5interface NodePair {
6  node1: number;
7  node2: number;
8}
9
10// Initialize the graph with the given pairs.
11function initializeGraph(pairs: NodePair[]): void {
12  pairs.forEach(pair => {
13    const { node1, node2 } = pair;
14    graph[node1][node2] = graph[node2][node1] = true;
15    adjacencyList[node1].push(node2);
16    adjacencyList[node2].push(node1);
17  });
18}
19
20// Creates and populates a list of nodes present in the graph.
21function populateNodesList(): number[] {
22  const nodesList: number[] = [];
23  for (let node = 1; node <= 500; ++node) {
24    if (adjacencyList[node].length) {
25      nodesList.push(node);
26      graph[node][node] = true; // A node is always connected to itself.
27    }
28  }
29  return nodesList;
30}
31
32// Sort the nodes based on the degree (number of neighbors), in ascending order.
33function sortNodesList(nodesList: number[]): void {
34  nodesList.sort((nodeX, nodeY) => adjacencyList[nodeX].length - adjacencyList[nodeY].length);
35}
36
37// CheckWays function determines the number of valid BSTs that can be formed from the given graph.
38function checkWays(pairs: NodePair[]): number {
39  initializeGraph(pairs);
40  const nodesList = populateNodesList();
41  sortNodesList(nodesList);
42
43  let hasEqualDegreeNodes = false; // Used to detect if there are two nodes with the same degree.
44  let rootCount = 0; // Counter to check how many possible root nodes we have.
45
46  // Iterate through each node to check if the graph can form a tree.
47  for (let i = 0; i < nodesList.length; ++i) {
48    const currentNode = nodesList[i];
49    let nextNodeIndex = i + 1;
50  
51    // Find the next node in the sorted list that is connected to the current node.
52    while (nextNodeIndex < nodesList.length && !graph[currentNode][nodesList[nextNodeIndex]]) {
53      ++nextNodeIndex;
54    }
55  
56    if (nextNodeIndex < nodesList.length) {
57      const nextNode = nodesList[nextNodeIndex];
58      // Check if the current and next nodes have the same degree.
59      if (adjacencyList[currentNode].length === adjacencyList[nextNode].length) {
60        hasEqualDegreeNodes = true;
61      }
62    
63      // Make sure all neighbors of the currentNode are connected to nextNode.
64      for (const neighbor of adjacencyList[currentNode]) {
65        if (!graph[nextNode][neighbor])
66          return 0; // Return 0 if the neighbor is not connected to the next node.
67      }
68
69    } else {
70      // If no connected node is found, increment root count as it might be a root.
71      rootCount++;
72    }
73  }
74
75  // If there is more than one root, it can’t form a tree.
76  if (rootCount > 1) return 0;
77
78  // If there are nodes with equal degrees, there are two ways to arrange the tree.
79  if (hasEqualDegreeNodes) return 2;
80
81  // If the execution reaches here, there is exactly one way to arrange the tree.
82  return 1;
83}
84

Time and Space Complexity

Time Complexity

The primary operations in this code are as follows:

  1. Looping over the pairs to fill the adjacency matrix g and create the adjacency list v. This has a time complexity of O(P), where P is the number of pairs.

  2. Looping over the range 510 to find and sort the nodes. The finding of nodes has a time complexity of O(N), where N is the total number of different nodes which could be up to 510 in the worst case.

  3. The sorting of nodes has a time complexity of O(N log N) due to the sort operation.

  4. The nested loops where it compares every x with y and iterates through all z in v[x]. In the worst case, this results in looping through all edges for each node, giving it a time complexity of O(N * P).

Given that the largest number of nodes is capped at 510, the overall time complexity is:

O(P + N log N + N * P) = O(P + N * P) = O(N * P), because N is fixed and small, we can consider it a constant and simplify to O(P).

Space Complexity

The space complexity consists of the storage for:

  1. The adjacency matrix g, which is a fixed size of 510x510. This constitutes a space complexity of O(1) as it does not grow with the input size.

  2. The adjacency list v, which can potentially have all pairs stored, resulting in a space complexity of O(P).

  3. The nodes list containing at most N elements, adding O(N) to the space complexity.

As a result, the overall space complexity is O(P + N) = O(P) because N is a fixed constant.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings