Tree Height After Deletions II
A rooted tree is given as [parent, child] edges plus its root. Deleting a node promotes its children to its nearest surviving ancestor, as in Tree Height After Deletions I. Height is counted in nodes.
Return a smallest set of non-root nodes whose deletion brings the height down to at most k (k ≥ 1). Any smallest set is accepted; return an empty list if the tree is already short enough.
edges = [[1, 2], [1, 3], [3, 4], [3, 5], [5, 6]], root = 1 // height 4
fewestDeletions(edges, 1, 2) -> [3, 5] // leaves 1 -> {2, 4, 6}
fewestDeletions(edges, 1, 4) -> []Hints
Hint 1
Compute each node's own height h[u] — the node-count height of its subtree in the original tree — with one post-order pass.
Hint 2
Delete every non-root node with h[u] ≥ k. Along any root-to-leaf path h strictly decreases, so the survivors below the root have distinct values in 1..k-1: at most k-1 of them, which is a height of at most k.
Hint 3
No smaller set works: a node taller than its remaining budget always has a descendant exactly at the budget, so deleting it never costs more than keeping it. The tree DP collapses to this count.