Tree Height Deletions
MediumTrees ยท Snowflake
Given a rooted tree as a parent array parent, return the minimum number of nodes to delete so that the tree's height is at most k.
parent[0] = -1 marks the root, and parent[i] is the parent of node i. The root cannot be deleted. Deleting any other node removes it and attaches each of its children to its parent. The height is the number of nodes on the longest root-to-leaf path.
Example 1
- Input:
- parent = [-1, 0, 1, 2, 3, 4, 5, 3, 7], k = 4
- Output:
- 3
- Explanation
- Deleting nodes 1, 2 and 3 leaves the root with children 4 and 7. The longest path is then 0, 4, 5, 6, which has 4 nodes.
Example 2
- Input:
- parent = [-1, 0, 0, 0, 1, 1], k = 2
- Output:
- 1
Example 3
- Input:
- parent = [-1, 0, 0, 0], k = 1
- Output:
- 3
Constraints
1 <= parent.length <= 10^4parent[0] = -1, andparentdescribes a valid tree rooted at node01 <= k <= parent.length- A parent's index may be larger than its child's index