Quick Overview

Given an N-ary tree in which deleting a node moves its children up to its parent, find the fewest deletions that bring the tree's height down to at most k, with the root never deleted. Tests reasoning about how deletions shorten root-to-leaf paths and turning that reasoning into an efficient pass over a large tree.

Fewest Node Deletions to Cap an N-ary Tree's Height at k

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

A rooted tree has `n` nodes numbered `0` to `n - 1`, and each node can have any number of children. Node `0` is the root. Deleting a node attaches its children to the deleted node's parent; if that parent is deleted as well, the children move up again, so after any set of deletions every remaining node hangs directly under its nearest ancestor that is not deleted. Given a limit `k`, return the minimum number of nodes you must delete so that the height of the remaining tree is at most `k`. In the interview, this was the follow-up to computing the height that remains after a given list of deletions. ### Function Signature ```python def min_deletions_for_height(parent: list[int], k: int) -> int: ``` `parent[i]` is the parent of node `i`, and `parent[0] == -1`. ### Rules - The height of a tree is the number of nodes on its longest path from the root down to a leaf. A tree that consists of the root alone has height 1. - The root can never be deleted. Every other node can. - Return only the minimum number of deletions, not which nodes to delete. If the height is already at most `k`, return 0. - An answer always exists: deleting every node except the root leaves height 1. ### Constraints - `1 <= len(parent) <= 10^5` - `parent[0] == -1`. For `i >= 1`, `0 <= parent[i] < len(parent)` and `parent[i] != i`, and following parents from any node reaches node `0`, so the input is a single tree. A parent's number may be larger than its child's. - `1 <= k <= len(parent)` - The tree may be a single path of `10^5` nodes. ### Examples **Example 1** ```text Input: parent = [-1, 0, 0, 1, 1, 3, 2], k = 3 Output: 1 ``` The tree has the edges 0 → 1, 0 → 2, 1 → 3, 1 → 4, 3 → 5 and 2 → 6. Its longest path, 0 → 1 → 3 → 5, has 4 nodes, so at least one deletion is needed. Deleting node 3 attaches node 5 to node 1, and every path then has at most 3 nodes. **Example 2** ```text Input: parent = [-1, 0, 1, 2, 3], k = 2 Output: 3 ``` The tree is a path of 5 nodes. Each deletion shortens it by exactly one node, so 3 deletions are needed to bring it down to 2 nodes. **Example 3** ```text Input: parent = [-1, 0, 0, 1, 1, 3, 2, 6], k = 3 Output: 2 ``` The paths 0 → 1 → 3 → 5 and 0 → 2 → 6 → 7 each have 4 nodes and share only the root, which cannot be deleted, so no single deletion shortens both. Deleting nodes 3 and 6, for example, leaves height 3.

Overview: Given an N-ary tree in which deleting a node moves its children up to its parent, find the fewest deletions that bring the tree's height down to at most k, with the root never deleted. Tests reasoning about how deletions shorten root-to-leaf paths and turning that reasoning into an efficient pass over a large tree.

A rooted tree has `n` nodes numbered `0` to `n - 1`, and each node can have any number of children. Node `0` is the root. You are given the array `parent`, where `parent[i]` is the parent of node `i` and `parent[0] == -1`. Deleting a node attaches its children to the deleted node's parent; if that parent is deleted as well, the children move up again. So after any set of deletions, every remaining node hangs directly under its nearest ancestor that is not deleted. Given a limit `k`, return the minimum number of nodes you must delete so that the height of the remaining tree is at most `k`. ### Rules - The height of a tree is the number of nodes on its longest path from the root down to a leaf. A tree that consists of the root alone has height 1. - The root can never be deleted. Every other node can. - Return only the minimum number of deletions, not which nodes to delete. If the height is already at most `k`, return 0. - An answer always exists: deleting every node except the root leaves height 1. - The answer is an integer between 0 and `n - 1`, so it never exceeds 2^31 - 1. ### Example 1 ```text Input: parent = [-1, 0, 0, 1, 1, 3, 2], k = 3 Output: 1 ``` The tree has the edges 0 → 1, 0 → 2, 1 → 3, 1 → 4, 3 → 5 and 2 → 6. Its longest path, 0 → 1 → 3 → 5, has 4 nodes, so at least one deletion is needed. Deleting node 3 attaches node 5 to node 1, and every path then has at most 3 nodes. ### Example 2 ```text Input: parent = [-1, 0, 0, 1, 1, 3, 2, 6], k = 3 Output: 2 ``` The paths 0 → 1 → 3 → 5 and 0 → 2 → 6 → 7 each have 4 nodes and share only the root, which cannot be deleted, so no single deletion shortens both. Deleting nodes 3 and 6, for example, leaves height 3. ### Constraints - `1 <= len(parent) <= 10^5` - `parent[0] == -1`. For `i >= 1`, `0 <= parent[i] < len(parent)` and `parent[i] != i`, and following parents from any node reaches node `0`, so the input is a single tree. A parent's number may be larger than its child's. - `1 <= k <= len(parent)` - The tree may be a single path of `10^5` nodes.

Constraints

  • 1 <= len(parent) <= 10^5
  • parent[0] == -1
  • For i >= 1, 0 <= parent[i] < len(parent) and parent[i] != i, and following parents from any node reaches node 0, so the input is a single tree
  • A parent's number may be larger than its child's
  • 1 <= k <= len(parent)
  • The tree may be a single path of 10^5 nodes
  • The answer lies in [0, len(parent) - 1] and fits in a 32-bit signed integer

Examples

Input: ([-1], 1)

Expected Output: 0

Explanation: Minimum valid input: the root alone has height 1, which is already within k = 1.

Input: ([-1, 0], 1)

Expected Output: 1

Explanation: Two-node path with k = 1: the height is 2 nodes, so node 1 must go. Counting edges instead of nodes would wrongly return 0.

Hints

  1. After any set of deletions, the remaining height is the largest number of kept nodes on one original root-to-leaf path, and the root always counts as one of them.
  2. Look at a single downward path below the root: how many of its nodes can stay? Then ask which nodes sit on many long paths at once, so that one deletion helps all of them.
  3. The tree can be a single path of 10^5 nodes and parent numbers can be larger than child numbers, so do not rely on deep recursion or on index order.

Loading coding console...

Show the approach

Approach

Let h(v) be the number of nodes on the longest downward path that starts at v (a leaf has h = 1). After deletions every kept node hangs under its nearest kept ancestor, so the remaining height equals the largest number of kept nodes on any original root-to-leaf path. The root is always kept, so every downward path that starts below the root may keep at most k - 1 nodes.

Claim: the answer is the number of non-root nodes v with h(v) >= k.

Feasibility: keep the root and exactly the non-root nodes with h(v) <= k - 1. h strictly decreases as you walk down a path, so the kept nodes on any root-to-leaf path have distinct h values in 1..k-1: at most k - 1 of them plus the root, i.e. height at most k.

Optimality: split the nodes below the root into long-path chains: start a chain at any node t that is not already covered and repeatedly step to a child of maximum h. That chain is a downward path of exactly h(t) nodes whose h values are h(t), h(t) - 1, ..., 1, and every non-root node lies on exactly one chain. Any valid deletion set keeps at most k - 1 nodes of each chain, so it deletes at least max(0, h(t) - (k - 1)) of them, which is exactly the number of that chain's nodes with h >= k. Summing over the chains gives the same count as a lower bound, so the count is optimal.

Implementation: build child lists from parent, produce a breadth-first order from the root iteratively (a 10^5-node path would overflow a recursive DFS), then walk that order backwards so every child's h is final before it updates its parent: h[parent] = max(h[parent], h[child] + 1). Finally count the non-root nodes with h >= k.

Edge cases: a single node returns 0; k = 1 returns n - 1 because every non-root node has h >= 1; a tree already within k returns 0 because every non-root node has h <= height - 1 <= k - 1; parent numbers larger than child numbers are handled because the order comes from the BFS, not from node numbers.

Time complexity:
O(n)
Space complexity:
O(n)