310. Minimum Height Trees

MediumDepth-First SearchBreadth-First SearchGraphTopological Sort
Leetcode Link

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:

  1. n: the number of nodes in the tree, where the nodes are labeled from 0 to n - 1, and
  2. edges: an array of n - 1 edges with each edge given as a pair [a_i, b_i] representing an undirected connection between nodes a_i and b_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.

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:

  1. Identify all the leaf nodes (nodes with only one connection) in the tree.
  2. Remove the leaf nodes from the tree, along with their edges, to expose a new layer of leaf nodes.
  3. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

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:

  1. Handle the special case for a single-node tree: If n == 1, the tree has only one node and no edges, so that node (labeled 0) is by definition the root of an MHT. The function returns a list containing just this node.

  2. Prepare data structures:

    • A graph g is represented using a defaultdict(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 of n initialized to 0, which will keep track of the number of edges connected to each node (i.e., the degree of the node).

  3. Populate the graph and degree:

    • For each edge (a, b) in the edges list, add b to the adjacency list of a (i.e., g[a].append(b)) and vice versa because the graph is undirected. Increment the degree of both a and b since the edge contributes to the degree of each.

  4. Initialize a queue with all leaf nodes:

    • A double-ended queue q (deque) is initialized with all nodes that have a degree of 1, which means they are leaves.

  5. Process the tree using BFS to remove leaves:

    • While q is not empty meaning there are still leaves to remove, clear the list ans to prepare for a new set of leaves.
    • Iterate over the current size of q, representing the current level of leaves to remove. Use q.popleft() to remove and get the first leaf a.
    • Add a to the current answer list ans.
    • For each adjacent node b of a, decrease its degree in degree[b] as we're going to remove the edge (a, b). If b becomes a new leaf (degree of 1), add it to q for the next iteration.

  6. 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.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Example 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 nodes 0, 1, 2, 3, 4, 5.
  • edges = [[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]].

The tree can be visualized as follows:

1   0
2   |
3   3
4 / | \
51  |  4
6   |   \
7   2    5

Following the solution approach:

  1. Handle the special case for a single-node tree: Since n != 1, this step is skipped.

  2. Prepare data structures:

    • We create a graph g and a list degree with n entries initialized to 0.

  3. 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 nodes 0, 1, 2, 5 are connected to one node, 4 is connected to two nodes, and 3 is connected to four nodes.

  4. Initialize a queue with all leaf nodes:

    • Our queue q will be initialized with [0, 1, 2, 5] as they have a degree of 1.

  5. 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 removing 0, the degree of 3 becomes 3. This is similarly done for 1, and 2. Lastly, removing 5 reduces the degree of 4 to 1, 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.

  6. Finish when central nodes are found:

    • After the second iteration, removing 4 from the queue makes 3 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.

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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following array represent a max heap?

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 takes O(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 of O(E) if we consider memory for the adjacency list alone.
  • The degree array consumes O(V) space, storing the degree of each vertex.
  • The queue q can hold all vertices at most, so it consumes O(V) space.
  • The ans list, in the worst case, can hold all nodes, thus consuming O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Recommended Readings

DFS Fundamentals

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

BFS Fundamentals

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

Graph Fundamentals

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

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ