Leetcode 310: Minimum Height Trees
Solution to LeetCode 310: Minimum Height Trees Problem
You are given a tree with ’n’ nodes labeled from 0 to n-1, represented by ’n-1’ edges. Your task is to find all roots that minimize the height of the tree. The height of a tree is defined as the number of edges in the longest downward path from the root to any leaf.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer 'n' and a list of 'n-1' edges that define the tree.
Example: n = 5, edges = [[1, 0], [1, 2], [2, 3], [2, 4]]
Constraints:
• 1 <= n <= 20,000
• edges.length == n - 1
• 0 <= ai, bi < n
• ai != bi
• All pairs (ai, bi) are distinct
• The input is guaranteed to be a valid tree
Output: The output should be a list of integers representing the nodes that minimize the height of the tree.
Example: [2]
Constraints:
• The output list can have one or more nodes.
Goal: Find the nodes that minimize the height of the tree by iterating from leaf nodes towards the center of the tree.
Steps:
• Create an adjacency list representation of the tree.
• Track the degree of each node to identify leaf nodes.
• Remove leaf nodes iteratively to find the center(s) of the tree (or minimum height roots).
• Nodes remaining after iterating through the process are the minimum height tree roots.
Goal: The solution needs to handle trees with up to 20,000 nodes efficiently.
Steps:
• Ensure the algorithm works efficiently for large values of 'n'.
• Handle edge cases such as linear trees or balanced trees.
Assumptions:
• The input tree is always valid and is guaranteed to contain no cycles.
• The input edges will always form a connected tree.
• Input: n = 5, edges = [[1, 0], [1, 2], [2, 3], [2, 4]]
• Explanation: Rooting the tree at node 2 minimizes the height, as it is centrally located.
• Input: n = 6, edges = [[3, 0], [3, 1], [3, 2], [3, 4], [5, 4]]
• Explanation: Nodes 3 and 4 minimize the height of the tree, resulting in a height of 2.
• Input: n = 7, edges = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]
• Explanation: Node 3 minimizes the tree height as it is the center of this linear tree.
Approach: The problem can be solved by progressively removing leaf nodes until only the central nodes remain, which are the roots of the minimum height trees.
Observations:
• The tree is undirected and connected, which allows for a unique path between any two nodes.
• The height of the tree is minimized when the root is as central as possible, which can be found by peeling off leaf nodes.
Steps:
• Represent the tree using an adjacency list.
• Track the degree of each node and push leaf nodes into a queue.
• Iteratively remove leaf nodes from the tree until one or two nodes remain, which will be the minimum height tree roots.
Empty Inputs:
• There is no need to handle empty inputs, as the problem guarantees a valid tree with at least one node.
Large Inputs:
• The solution must efficiently handle the maximum constraint of n = 20,000.
Special Values:
• If the tree is a line (i.e., a path), the root is the middle node(s).
Constraints:
• Ensure the solution works in O(n) time to handle large inputs.
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
if(n == 1) return {0};
vector<vector<int>> adj(n);
vector<int> degree(n, 0);
for(auto e: edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
degree[e[0]]++;
degree[e[1]]++;
}
queue<int> q;
for(int i = 0; i < n; i++)
if(degree[i] == 1)
q.push(i);
vector<int> res;
while(!q.empty()) {
res.clear();
int sz = q.size();
while(sz--) {
int tmp = q.front();
q.pop();
res.push_back(tmp);
for(auto nbr: adj[tmp]) {
degree[nbr]--;
if(degree[nbr] == 1)
q.push(nbr);
}
}
}
return res;
}
1 : Function Definition
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
Define the function that accepts the number of nodes `n` and a vector of edges representing an undirected graph.
2 : Base Case
if(n == 1) return {0};
If there is only one node, return it as the result since it's trivially the minimum height tree.
3 : Graph Initialization
vector<vector<int>> adj(n);
Create an adjacency list to represent the graph, where each node points to its neighbors.
4 : Degree Initialization
vector<int> degree(n, 0);
Initialize a degree array to keep track of the number of connections (edges) each node has.
5 : Graph Construction
for(auto e: edges) {
Iterate over all edges to build the adjacency list and update the degree of each node.
6 : Edge Insertion
adj[e[0]].push_back(e[1]);
For each edge, add the neighboring node to the adjacency list of the first node.
7 : Edge Insertion
adj[e[1]].push_back(e[0]);
Similarly, add the neighboring node to the adjacency list of the second node.
8 : Degree Update
degree[e[0]]++;
Increase the degree of the first node.
9 : Degree Update
degree[e[1]]++;
Increase the degree of the second node.
10 : Queue Initialization
queue<int> q;
Initialize a queue to perform a breadth-first search (BFS) from the leaf nodes.
11 : Queue Population
for(int i = 0; i < n; i++)
Iterate through all the nodes to find those with only one connection (degree 1), which are leaves.
12 : Queue Population
if(degree[i] == 1)
Check if the current node is a leaf node (degree 1).
13 : Queue Population
q.push(i);
Push leaf nodes into the queue to start the BFS process.
14 : Result Initialization
vector<int> res;
Initialize an empty result vector to store the nodes that will form the minimum height trees.
15 : BFS Loop
while(!q.empty()) {
Start the BFS loop to process the leaf nodes and iteratively remove them.
16 : Clear Result
res.clear();
Clear the result vector to store the next set of leaf nodes.
17 : Queue Size
int sz = q.size();
Get the size of the current level of the BFS queue.
18 : BFS Inner Loop
while(sz--) {
Process all the nodes at the current level.
19 : Queue Front
int tmp = q.front();
Get the current node from the front of the queue.
20 : Queue Pop
q.pop();
Remove the current node from the queue.
21 : Result Update
res.push_back(tmp);
Add the current node to the result vector.
22 : Neighbor Processing
for(auto nbr: adj[tmp]) {
Process all the neighbors of the current node.
23 : Degree Update
degree[nbr]--;
Decrease the degree of the neighboring node.
24 : Leaf Detection
if(degree[nbr] == 1)
Check if the neighboring node has become a leaf (degree 1).
25 : Queue Update
q.push(nbr);
Add the neighbor to the queue if it has become a leaf.
26 : BFS End
}
End the main BFS loop.
27 : Return Result
return res;
Return the list of nodes that form the minimum height trees.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) as each node is processed at most once.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the storage of the adjacency list and degree array.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus