How should I practice Minimum N-ary Tree Depth Deletions?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Snowflake phone screen problems in FastPrep.

Is Minimum N-ary Tree Depth Deletions associated with Snowflake?

FastPrep tags this as a Snowflake phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Tree

Minimum N-ary Tree Depth Deletions

Learn this problem

● Medium

SnowflakeFULLTIMEPHONE SCREEN

See Snowflake hiring insights

Problem statement

You are given a rooted n-ary tree with nodes labeled from 1 through n. Node 1 is the root. For every node i from 2 through n, parent[i - 2] is the ID of its parent.

The root has depth 1. You may repeatedly delete a current non-root leaf. After every deletion, the remaining nodes must still form one rooted tree with root 1.

Return the node IDs in the unique minimum deletion set that makes the tree's maximum depth at most k. Return the IDs in ascending order. If the tree already has maximum depth at most k, return an empty array.

A node whose original depth is greater than k must eventually be deleted. Conversely, deleting exactly those nodes is valid: process them from greatest depth toward the root, so every selected node is a leaf when it is removed.

Function

minimumDepthDeletions(parent: int[], k: int) → int[]

Examples

Example 1

parent = [1,1,2,2,3,4]k = 3return = [7]

Nodes 4, 5, and 6 have depth 3, while node 7 has depth 4. Deleting leaf 7 is necessary and sufficient.

Example 2

parent = [1,2,3,4]k = 2return = [3,4,5]

The tree is the chain 1 - 2 - 3 - 4 - 5. Nodes 3, 4, and 5 are deeper than 2. They can be removed in the operational order 5, 4, 3; the returned set is sorted by ID.

Example 3

parent = [1,1,1]k = 1return = [2,3,4]

Every child of the root has depth 2, so all three current leaves must be deleted to leave a tree of depth 1.

Constraints

0 <= parent.length <= 199999.
The tree has n = parent.length + 1 nodes labeled from 1 through n.
For each node i from 2 through n, 1 <= parent[i - 2] <= n, and the parent array describes one valid rooted tree with root 1.
1 <= k <= n.
Only current non-root leaves may be deleted, and the returned node IDs must be in ascending order.