D
DevExCode

LeetCode 310: Minimum Height Trees Solution

Master LeetCode problem 310 (Minimum Height Trees), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To find the minimum height trees (MHTs) in a given tree, we can use a two-step process:

  1. Trimming Leaves: We iteratively remove the leaf nodes (nodes with only one neighbor) from the tree until only 1 or 2 nodes are left.
  2. BFS from Leaves: Starting from the remaining nodes (1 or 2), we perform a Breadth First Search (BFS) to find the MHTs.

Algorithm:

  1. Create an adjacency list representing the tree.
  2. Initialize a queue with all leaf nodes.
  3. Remove the leaf nodes from the tree and update the degrees of their neighbors.
  4. Add new leaf nodes (nodes with updated degree = 1) to the queue.
  5. Repeat steps 3-4 until only 1 or 2 nodes are left.
  6. Perform BFS from the remaining nodes to find MHTs.

Time Complexity: O(n), where n is the number of nodes in the tree. Space Complexity: O(n), to store the adjacency list and queue.

:

Solution Code

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) {
            return Collections.singletonList(0);
        }

        List<Set<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new HashSet<>());
        }

        int[] degree = new int[n];
        for (int[] edge : edges) {
            adjList.get(edge[0]).add(edge[1]);
            adjList.get(edge[1]).add(edge[0]);
            degree[edge[0]]++;
            degree[edge[1]]++;
        }

        Queue<Integer> leaves = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                leaves.offer(i);
            }
        }

        while (n > 2) {
            int leavesSize = leaves.size();
            n -= leavesSize;
            for (int i = 0; i < leavesSize; i++) {
                int leaf = leaves.poll();
                for (int neighbor : adjList.get(leaf)) {
                    degree[neighbor]--;
                    if (degree[neighbor] == 1) {
                        leaves.offer(neighbor);
                    }
                }
            }
        }

        List<Integer> result = new ArrayList<>(leaves);
        return result;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 310 (Minimum Height Trees)?

This page provides optimized solutions for LeetCode problem 310 (Minimum Height Trees) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 310 (Minimum Height Trees)?

The time complexity for LeetCode 310 (Minimum Height Trees) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 310 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 310 in Java, C++, or Python.

Back to LeetCode Solutions