Minimum Prunes to Bring a Filesystem Tree's Depth Under a Limit

A filesystem snapshot is represented as n directories numbered 0 to n - 1, where directory 0 is the root and every other directory has exactly one parent directory, with any number of subdirectories of its own. Deleting a directory does not delete its contents: every subdirectory it contained is reattached directly under its own parent directory. Deleting the directory whose parent was itself already deleted simply continues the chain — a subdirectory always ends up directly under the nearest surviving ancestor directory.

Given a maximum allowed nesting depth k, return the fewest directory deletions needed so that the deepest remaining path from the root is at most k directories long. The root can never be deleted.

Function Signature

def min_deletions_for_max_depth(parent: list[int], k: int) -> int:

parent[i] is the index of directory i's parent, and parent[0] == -1.

Rules

• The depth of a path is the count of directories on it, root included; a snapshot consisting of the root alone has depth 1.
• The root (directory 0) is never a candidate for deletion. Every other directory may be deleted.
• Return only the count of deletions, not which directories to delete. If the deepest path is already at most k, the answer is 0.
• A solution always exists, since deleting every non-root directory leaves a snapshot of depth 1.

Constraints

• 1 <= len(parent) <= 10^5
• parent[0] == -1; for every i >= 1, 0 <= parent[i] < len(parent), parent[i] != i, and repeatedly following parents from any directory eventually reaches directory 0 — the input is guaranteed to form a single valid tree. A directory's parent index is not required to be smaller than its own index.
• 1 <= k <= len(parent)
• The snapshot may be a single unbranching chain of up to 10^5 directories.

Example 1

parent = [-1, 0, 0, 0, 1, 4, 5, 2], k = 3
Output: 2

Edges: 0->1, 0->2, 0->3, 1->4, 4->5, 5->6, 2->7. The deepest path is 0 -> 1 -> 4 -> 5 -> 6, 5 directories long. Deleting directory 4 reattaches 5 directly under 1, giving the path 0 -> 1 -> 5 -> 6 (4 directories) — still too deep. Deleting directory 5 as well reattaches 6 directly under 1, giving 0 -> 1 -> 6, 3 directories, which satisfies k = 3. No single deletion can bring this chain down to 3, so 2 is minimal.

Example 2

parent = [-1, 0, 1, 2, 3, 4], k = 3
Output: 3

The snapshot is one unbranching chain of 6 directories. Every deletion shortens the remaining chain by exactly one directory, so reaching depth 3 from depth 6 takes exactly 3 deletions.

Example 3

parent = [-1, 0, 1, 2, 0, 4, 5], k = 3
Output: 2

Two chains of depth 4 hang off the root and share nothing but the root itself (0 -> 1 -> 2 -> 3 and 0 -> 4 -> 5 -> 6). A single deletion can only shorten one of the two chains, so each needs its own deletion to come down to depth 3, for a total of 2.