310. Minimum Height Trees
Problem Description
In this LeetCode problem, we're given what is known as a tree in the context of graph theory. A tree is a type of graph where there is exactly one path between any two nodes, and, importantly, there are no cycles, meaning no path starts and ends at the same node unless the path is zero-length (does not move from the starting node).
We are provided with two inputs:
n
: the number of nodes in the tree, where the nodes are labeled from0
ton - 1
, andedges
: an array ofn - 1
edges with each edge given as a pair[a_i, b_i]
representing an undirected connection between nodesa_i
andb_i
.
The task is to pick a node that, when used as the root, results in a tree of the minimum possible height. The height of a tree, in this case, is defined as the number of edges in the longest path from the chosen root to any leaf node (a leaf node is a node with no children).
We are asked not just to find the height but to return a list of the labels of all nodes that can serve as roots for such minimum height trees (MHTs). There can be more than one MHT and we need to list all of their root labels.
Flowchart Walkthrough
First, let's analyze the problem using the Flowchart. Here's a step-by-step walkthrough for LeetCode 310. Minimum Height Trees:
Is it a graph?
- Yes: We're given an undirected graph where nodes represent towns and edges represent roads.
Is it a tree?
- Yes: An undirected graph that is connected and has (n) nodes and (n-1) edges is a tree.
Applying Depth-First Search (DFS) in trees are commonly used for traversing or searching tree structures, finding connectivity, and computing other properties directly related to the structure.
Conclusion: The flowchart would suggest using the DFS approach for this tree problem. This can be effective in traversing or implementing algorithms to find nodes that lead to minimum height trees, considering DFS allows exploring each branch before moving to the next.
Intuition
The key insight for solving this problem is understanding that the root of an MHT will be near the center of the tree. If we pick a node on the periphery of the tree (like a leaf), the height will be larger because it takes more edges to reach the opposite side of the tree. The MHTs can be found by iteratively trimming the leaves until one or two nodes remain, which will be our answer.
The process is somewhat similar to peeling an onion; we remove the outer layer (leaves) one by one until we reach the core. Here's how it breaks down:
- Identify all the leaf nodes (nodes with only one connection) in the tree.
- Remove the leaf nodes from the tree, along with their edges, to expose a new layer of leaf nodes.
- Repeat the process until one or two nodes remain. These nodes will be the roots of the MHTs.
Why one or two? Because if a tree has an odd number of nodes, there will be one center node, while a tree with an even number of nodes could have two central nodes.
The provided solution translates this approach into code. A breadth-first search (BFS) is employed for the trimming process. A queue is used to process and trim leaves level by level, and the degree of each node is tracked to easily identify the leaves. When only one or two nodes are left, we've found our roots for the MHTs.
Learn more about Depth-First Search, Breadth-First Search, Graph and Topological Sort patterns.
Solution Approach
The implementation uses a breadth-first search (BFS) to trim the leaves from the tree iteratively. Here are the steps in the implementation along with the relevant data structures and algorithms used:
-
Handle the special case for a single-node tree: If
n == 1
, the tree has only one node and no edges, so that node (labeled0
) is by definition the root of an MHT. The function returns a list containing just this node. -
Prepare data structures:
- A graph
g
is represented using adefaultdict(list)
. This provides an adjacency list representation where each node has a list of its adjacent nodes. - A list
degree
is created with the length ofn
initialized to0
, which will keep track of the number of edges connected to each node (i.e., the degree of the node).
- A graph
-
Populate the graph and degree:
- For each edge
(a, b)
in theedges
list, addb
to the adjacency list ofa
(i.e.,g[a].append(b)
) and vice versa because the graph is undirected. Increment the degree of botha
andb
since the edge contributes to the degree of each.
- For each edge
-
Initialize a queue with all leaf nodes:
- A double-ended queue
q
(deque
) is initialized with all nodes that have a degree of1
, which means they are leaves.
- A double-ended queue
-
Process the tree using BFS to remove leaves:
- While
q
is not empty meaning there are still leaves to remove, clear the listans
to prepare for a new set of leaves. - Iterate over the current size of
q
, representing the current level of leaves to remove. Useq.popleft()
to remove and get the first leafa
. - Add
a
to the current answer listans
. - For each adjacent node
b
ofa
, decrease its degree indegree[b]
as we're going to remove the edge(a, b)
. Ifb
becomes a new leaf (degree of1
), add it toq
for the next iteration.
- While
-
Finish when central nodes are found:
- When the while loop exits,
ans
will contain either one or two nodes, which will be the roots of the MHT(s). These are returned as the result.
- When the while loop exits,
This approach efficiently prunes the tree layer by layer until reaching the center, ensuring a time complexity that is linear with respect to the number of nodes and edges, and thus suitable for large trees.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through the solution approach using a small example tree with 6 nodes. Assume the following input is given:
n = 6
, so we have nodes0, 1, 2, 3, 4, 5
.edges = [[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]
.
The tree can be visualized as follows:
0 | 3 / | \ 1 | 4 | \ 2 5
Following the solution approach:
-
Handle the special case for a single-node tree: Since
n != 1
, this step is skipped. -
Prepare data structures:
- We create a graph
g
and a listdegree
withn
entries initialized to0
.
- We create a graph
-
Populate the graph and degree:
g[0]
will have[3]
,g[3]
will have[0, 1, 2, 4]
, and so on.- The
degree
list will be[1, 1, 1, 4, 2, 1]
after this step since nodes0, 1, 2, 5
are connected to one node,4
is connected to two nodes, and3
is connected to four nodes.
-
Initialize a queue with all leaf nodes:
- Our queue
q
will be initialized with[0, 1, 2, 5]
as they have a degree of1
.
- Our queue
-
Process the tree using BFS to remove leaves:
- In the first iteration, each node in
q
(0, 1, 2, 5
) is a leaf and will be removed. When removing0
, the degree of3
becomes3
. This is similarly done for1
, and2
. Lastly, removing5
reduces the degree of4
to1
, making it a leaf. - After the first iteration, our updated
degree
list is[0, 0, 0, 1, 1, 0]
(we do not care about zeros as these are removed nodes).q
is now updated to[4, 3]
since these nodes have become leaves.
- In the first iteration, each node in
-
Finish when central nodes are found:
- After the second iteration, removing
4
from the queue makes3
have a degree of 0, which means it can no longer be reduced. We've found our central nodes, which in this case, is just one node,3
.
- After the second iteration, removing
The final answer list, which is the root of the MHT, will be [3]
. Therefore, node 3
can be chosen as the optimal root for the minimum height tree, resulting in a height of 2.
Solution Implementation
1from collections import defaultdict, deque
2from typing import List
3
4class Solution:
5 def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
6 # Base case: if there is only one node, return it as the centroid
7 if n == 1:
8 return [0]
9
10 # Initialize a graph and a degree list to store the degree of each node
11 graph = defaultdict(list)
12 degree = [0] * n
13
14 # Build the graph and keep track of each node's degree
15 for node1, node2 in edges:
16 graph[node1].append(node2)
17 graph[node2].append(node1)
18 degree[node1] += 1
19 degree[node2] += 1
20
21 # Initialize a queue with all leaf nodes (nodes with degree 1)
22 leaves_queue = deque(i for i in range(n) if degree[i] == 1)
23 min_height_trees = []
24
25 # Keep trimming leaves until the centroid/s is/are found
26 while leaves_queue:
27 min_height_trees.clear()
28 # Process all current leaves
29 for _ in range(len(leaves_queue)):
30 current_node = leaves_queue.popleft()
31 min_height_trees.append(current_node)
32 # Update the degrees of the current node's neighbors
33 for neighbor in graph[current_node]:
34 degree[neighbor] -= 1
35 # If the neighbor has become a leaf, add it to the queue for processing in the next round
36 if degree[neighbor] == 1:
37 leaves_queue.append(neighbor)
38
39 # Return the final centroids of the tree, which will have minimum height
40 return min_height_trees
41
1import java.util.*;
2
3class Solution {
4 public List<Integer> findMinHeightTrees(int n, int[][] edges) {
5 // List for storing the result which are the root nodes of the MHTs
6 List<Integer> minHeightTrees = new ArrayList<>();
7
8 // Base case: when there's only one node, return it as the root
9 if (n == 1) {
10 minHeightTrees.add(0);
11 return minHeightTrees;
12 }
13
14 // Initialize the adjacency list
15 List<Integer>[] adjacencyList = new List[n];
16 for (int i = 0; i < n; i++) {
17 adjacencyList[i] = new ArrayList<>();
18 }
19
20 // Initialize the degree array to keep track of the degree of each node
21 int[] degrees = new int[n];
22
23 // Build the graph by populating the adjacency list and degree array
24 for (int[] edge : edges) {
25 int nodeA = edge[0];
26 int nodeB = edge[1];
27
28 adjacencyList[nodeA].add(nodeB);
29 adjacencyList[nodeB].add(nodeA);
30
31 degrees[nodeA]++;
32 degrees[nodeB]++;
33 }
34
35 // Queue for holding the leaves nodes
36 Queue<Integer> leavesQueue = new LinkedList<>();
37
38 // Add initial leaves to queue - those are nodes with degree 1
39 for (int i = 0; i < n; i++) {
40 if (degrees[i] == 1) {
41 leavesQueue.offer(i);
42 }
43 }
44
45 // Process leaves until there are potentially 2 or less nodes left
46 while (!leavesQueue.isEmpty()) {
47 // Clear the previous result
48 minHeightTrees.clear();
49
50 // Number of leaves at the current level
51 int leavesCount = leavesQueue.size();
52
53 // Process each leaf node
54 for (int i = 0; i < leavesCount; i++) {
55 int leafNode = leavesQueue.poll();
56
57 // Add the leaf node to the result
58 minHeightTrees.add(leafNode);
59
60 // Visit all neighboring nodes
61 for (int neighbor : adjacencyList[leafNode]) {
62 // Decrease the degree as we are removing the leaf node
63 degrees[neighbor]--;
64 // If this makes the neighbor a new leaf, add it to queue
65 if (degrees[neighbor] == 1) {
66 leavesQueue.offer(neighbor);
67 }
68 }
69 }
70 }
71
72 // Returns the list of rooted trees with minimal height
73 return minHeightTrees;
74 }
75}
76
1#include <vector>
2#include <queue>
3
4using std::vector;
5using std::queue;
6
7class Solution {
8public:
9 // Function to find the nodes that form trees with the minimum height
10 vector<int> findMinHeightTrees(int numNodes, vector<vector<int>>& edges) {
11 // Base case: if there's only one node, it's the root of a minHeightTree
12 if (numNodes == 1) return {0};
13
14 // Each node will be an index in an adjacency list
15 vector<vector<int>> adjacencyList(numNodes);
16 // The degree count for each node
17 vector<int> degrees(numNodes, 0);
18
19 // Construct the graph
20 for (const auto& edge : edges) {
21 int nodeA = edge[0], nodeB = edge[1];
22 adjacencyList[nodeA].push_back(nodeB);
23 adjacencyList[nodeB].push_back(nodeA);
24 degrees[nodeA]++;
25 degrees[nodeB]++;
26 }
27
28 // Initialize a queue for processing leaf nodes (nodes with degree 1)
29 queue<int> processingQueue;
30 for (int i = 0; i < numNodes; ++i) {
31 if (degrees[i] == 1) {
32 processingQueue.push(i);
33 }
34 }
35
36 // Vector to hold the minimum height tree roots
37 vector<int> minHeightRoots;
38
39 // Process the graph
40 while (!processingQueue.empty()) {
41 // Start a new level
42 minHeightRoots.clear();
43 int levelSize = processingQueue.size(); // Number of nodes in the current level
44
45 // Process all nodes in the current level
46 for (int i = 0; i < levelSize; ++i) {
47 int currentNode = processingQueue.front();
48 processingQueue.pop();
49
50 // Add the current node to this level's results
51 minHeightRoots.push_back(currentNode);
52
53 // Decrease the degree of adjacent nodes and enqueue new leaf nodes
54 for (int adjacentNode : adjacencyList[currentNode]) {
55 if (--degrees[adjacentNode] == 1) { // If it becomes a leaf node
56 processingQueue.push(adjacentNode);
57 }
58 }
59 }
60 }
61
62 // minHeightRoots now contains the roots of tree who have the minimum height
63 return minHeightRoots;
64 }
65};
66
1type GraphEdge = [number, number];
2
3// Function to find the nodes that form trees with the minimum height
4function findMinHeightTrees(numNodes: number, edges: GraphEdge[]): number[] {
5 // Base case: if there's only one node, it's the root of a minHeightTree
6 if (numNodes === 1) return [0];
7
8 // Each node will be an index in an adjacency list
9 const adjacencyList: number[][] = Array.from({ length: numNodes }, () => []);
10 // The degree count for each node
11 const degrees: number[] = new Array(numNodes).fill(0);
12
13 // Construct the graph
14 for (const edge of edges) {
15 const [nodeA, nodeB] = edge;
16 adjacencyList[nodeA].push(nodeB);
17 adjacencyList[nodeB].push(nodeA);
18 degrees[nodeA]++;
19 degrees[nodeB]++;
20 }
21
22 // Initialize a queue for processing leaf nodes (nodes with degree 1)
23 const processingQueue: number[] = [];
24 for (let i = 0; i < numNodes; ++i) {
25 if (degrees[i] === 1) {
26 processingQueue.push(i);
27 }
28 }
29
30 // Array to hold the minimum height tree roots
31 let minHeightRoots: number[] = [];
32
33 // Process the graph
34 while (processingQueue.length > 0) {
35 // Start a new level
36 minHeightRoots = [];
37 const levelSize = processingQueue.length; // Number of nodes in the current level
38
39 // Process all nodes in the current level
40 for (let i = 0; i < levelSize; ++i) {
41 const currentNode = processingQueue.shift()!;
42
43 // Add the current node to this level's results
44 minHeightRoots.push(currentNode);
45
46 // Decrease the degree of adjacent nodes and enqueue new leaf nodes
47 for (const adjacentNode of adjacencyList[currentNode]) {
48 if (--degrees[adjacentNode] === 1) {
49 // If it becomes a leaf node
50 processingQueue.push(adjacentNode);
51 }
52 }
53 }
54 }
55
56 // minHeightRoots now contains the roots of trees that have the minimum height
57 return minHeightRoots;
58}
59
Time and Space Complexity
Time Complexity
The time complexity of this algorithm is O(V + E)
, where V
is the number of vertices (or nodes) and E
is the number of edges. Here's the breakdown of the complexity:
- Constructing the graph takes
O(V + E)
time, since we go through all edges and insert both the edge connections into the graph representation. - Initializing the degree array takes
O(V)
time. - Initializing the queue
q
with all leaves takesO(V)
time in the worst case (when all nodes are leaves, except one or two). - The while loop processes each node once when it becomes a leaf, decrementing the degrees and potentially adding new leaves to the queue. Every edge is looked at exactly twice (once for each vertex it connects) over the entire runtime of the algorithm. So the complexity associated with this part is
O(E)
. - Therefore, the loop and ensuing operations are bounded by the total number of edges, making the overall time complexity
O(V + E)
as, in graph algorithms, we commonly take the sum of vertices and edge processing times.
Space Complexity
The space complexity of this code is also O(V + E)
, explained as follows:
- We are maintaining a graph representation (
g
) which stores a list of neighbors for each node, with worst-case space usage ofO(E)
if we consider memory for the adjacency list alone. - The
degree
array consumesO(V)
space, storing the degree of each vertex. - The queue
q
can hold all vertices at most, so it consumesO(V)
space. - The
ans
list, in the worst case, can hold all nodes, thus consumingO(V)
space.
Considering all storage aspects, the space complexity sums up to O(V + E)
, accounting for both the space taken by the graph representation and the auxiliary data structures used throughout the algorithm.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the maximum element can be found in:
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Want a Structured Path to Master System Design Too? Donāt Miss This!