Minimum Tree Diameter After Removing K Leaves
MathWorks● HardFULLTIMEOAProblem statement
You are given a tree with n nodes numbered 0 to n - 1, an integer k, and an array edges, where edges[i] = [u, v] is an undirected edge between nodes u and v.
Remove exactly k nodes, one at a time. Each removed node must be a leaf of the current tree: a node with exactly one neighbor among the nodes that are still present. After a leaf is removed, its neighbor may become a leaf, and it can then be removed too.
The diameter of a tree is the number of edges on its longest path. A tree with a single node has diameter 0. Return the minimum possible diameter of the tree that remains after the k removals.
Function
minimumDiameter(n: int, k: int, edges: int[][]) → intExamples
Example 1
n = 7k = 2edges = [[0,1],[1,2],[2,3],[3,4],[2,5],[5,6]]return = 3Node 2 has three branches: 2-1-0, 2-3-4, and 2-5-6. Remove the leaves 0 and 4. The nodes 1, 2, 3, 5, 6 remain, and the longest paths, such as 1-2-5-6, have 3 edges.
A diameter of 2 is impossible: it would need all 5 remaining nodes within one edge of a single middle node, but even node 2 has only 3 neighbors, so at most 4 nodes fit. The answer is 3.
Example 2
n = 5k = 3edges = [[0,1],[1,2],[2,3],[3,4]]return = 1Remove leaf 0. Node 1 is now a leaf, so remove it too. Then remove leaf 4. Nodes 2 and 3 remain, joined by one edge, so the diameter is 1. Any two nodes that remain must still be joined, so the answer cannot be 0.
Example 3
n = 4k = 0edges = [[0,1],[1,2],[1,3]]return = 2No node is removed. The longest paths, such as 0-1-2, have 2 edges, so the answer is 2.
Constraints
1 <= n <= 20000 <= k <= n - 1edges.length == n - 1edges[i].length == 20 <= edges[i][j] <= n - 1- The edges form a tree: there are no repeated edges or self-loops, and every pair of nodes is connected.