Minimum Height Trees

Medium Graphs Topological Sort Original on LeetCode

Reported atAdobe

Minimum Height Trees is a medium graphs problem solved with the topological sort pattern. The best approach, optimal (trim leaves layer by layer), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (bfs from every node) up.

Problem

You are given a tree with n nodes labelled 0 to n - 1 as a list of undirected edges. Any node can be picked as the root, and the height of the rooted tree is the number of edges on the longest downward path from the root to a leaf.

Return every node that, when chosen as the root, gives the smallest possible height. The labels can be returned in any order.

Examples

Example 1

Input
n = 5, edges = [[0, 1], [1, 2], [2, 3], [2, 4]]
Output
[1, 2]
Why
Rooted at 1 or at 2 the tree has height 2; every other root gives height 3.

Example 2

Input
n = 6, edges = [[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]
Output
[3, 4]
Why
Node 3 and node 4 each sit in the middle of the longest path 0-3-4-5, giving height 2.

Example 3

Input
n = 1, edges = []
Output
[0]
Why
A single node is its own root with height 0.

Constraints

  • 1 <= n <= 2 * 10^4
  • edges.length == n - 1
  • 0 <= a_i, b_i < n, a_i != b_i
  • The edges form a tree: connected, no cycles, no repeated edges.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (BFS from every node)O(n²)O(n)
Optimal (trim leaves layer by layer)O(n)O(n)

1Brute force (BFS from every node)

TimeO(n²)n BFS runs, each visiting all n nodes and n - 1 edges.
SpaceO(n)Adjacency list, queue and visited array are all O(n).

Try every node as the root. A BFS from that node gives the height (the number of BFS levels minus one). Keep the nodes with the smallest height.

  1. Build an adjacency list.
  2. For each node r, run a BFS and count levels to get the height when rooted at r.
  3. Track the minimum height and collect every node that reaches it.
class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        List<Integer> result = new ArrayList<>();
        int best = Integer.MAX_VALUE;
        for (int r = 0; r < n; r++) {
            boolean[] seen = new boolean[n];
            Deque<Integer> queue = new ArrayDeque<>();
            queue.add(r);
            seen[r] = true;
            int height = -1;
            while (!queue.isEmpty()) {
                height++;
                for (int size = queue.size(); size > 0; size--) {
                    int u = queue.poll();
                    for (int v : adj.get(u)) {
                        if (!seen[v]) {
                            seen[v] = true;
                            queue.add(v);
                        }
                    }
                }
            }
            if (height < best) {
                best = height;
                result.clear();
            }
            if (height == best) result.add(r);
        }
        return result;
    }
}

2Optimal (trim leaves layer by layer)

TimeO(n)Each node is removed once and each edge is looked at twice.
SpaceO(n)Adjacency list, degree array and the current layer.

The best roots are the center of the tree: the middle one or two nodes of its longest path. Find them by repeatedly removing every current leaf (degree 1) at the same time, like a topological sort from the outside in. When at most two nodes are left, those are the answer.

  1. If n <= 2, return all nodes.
  2. Build the adjacency list and the degree of every node; put all degree-1 nodes in the first leaf layer.
  3. While more than two nodes remain: subtract the leaf count from the remaining count, and for each leaf decrease its neighbour's degree; neighbours that drop to degree 1 form the next layer.
  4. Return the last layer.
class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> leaves = new ArrayList<>();
        if (n <= 2) {
            for (int i = 0; i < n; i++) leaves.add(i);
            return leaves;
        }
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[] degree = new int[n];
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
            degree[e[0]]++;
            degree[e[1]]++;
        }
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) leaves.add(i);
        }
        int remaining = n;
        while (remaining > 2) {
            remaining -= leaves.size();
            List<Integer> next = new ArrayList<>();
            for (int leaf : leaves) {
                for (int v : adj.get(leaf)) {
                    degree[v]--;
                    if (degree[v] == 1) next.add(v);
                }
            }
            leaves = next;
        }
        return leaves;
    }
}

Edge cases to test

  • A single node with no edges: the answer is [0]
  • Two nodes: both are valid roots
  • A star: the center is the only answer
  • A long path: one middle node for an odd node count, two for an even count

Hints

Hint 1

Rooting at a leaf is never better than rooting at its neighbour (unless n <= 2). Which nodes can you rule out first?

Hint 2

Peel off all current leaves at once, then the new leaves, layer by layer, like an onion.

Hint 3

Stop when at most two nodes remain: the best roots are the middle of the longest path, and a path has one or two middles.

FAQ

What is the best time complexity for Minimum Height Trees?

Optimal (trim leaves layer by layer) runs in O(n) time and O(n) extra space. Each node is removed once and each edge is looked at twice.

Which pattern does Minimum Height Trees use?

It is a graphs problem that uses the topological sort pattern. Other problems with the same pattern: Topological sort using BFS, Course Schedule, Course Schedule II.

Is there a brute force solution for Minimum Height Trees?

Yes. Brute force (BFS from every node) takes O(n²) time and O(n) space. Try every node as the root.

Which edge cases should I test for Minimum Height Trees?

A single node with no edges: the answer is [0]; Two nodes: both are valid roots; A star: the center is the only answer; A long path: one middle node for an odd node count, two for an even count.