Height of an N-ary Tree After Deleting Nodes and Promoting Their Children
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a rooted N-ary tree and a set of nodes to delete. Deleting a node removes it from the tree, and its children are attached to its parent instead of being removed with it. Return the height of the tree after every deletion has been applied.
### Function Signature
```python
def height_after_deletions(parent: list[int], deleted: list[int]) -> int:
```
### Rules
- The tree has `n` nodes numbered `0` to `n - 1`. Node `0` is the root and `parent[0] == -1`. For every other node `i`, `parent[i]` is the index of its parent. Parents can have larger indices than their children.
- When a node is deleted, each of its children becomes a child of the deleted node's parent. If that parent is deleted too, the children keep moving up until they reach the nearest ancestor that is not deleted. The result does not depend on the order in which the deletions are applied.
- The root is never deleted.
- The height is the number of nodes on the longest path from the root down to any node, so a tree that consists of the root alone has height 1.
### Constraints
- `1 <= n == len(parent) <= 10^5`
- `parent[0] == -1`, and for `i >= 1`, `0 <= parent[i] <= n - 1`; the parent links form a single tree rooted at node `0` with no cycles.
- `0 <= len(deleted) <= n - 1`
- The values in `deleted` are distinct, each between `1` and `n - 1`.
- The tree can be a single path, so its depth can reach `n`.
### Examples
All three examples use this tree:
```text
parent = [-1, 0, 0, 1, 1, 3, 2]
0
/ \
1 2
/ \ \
3 4 6
|
5
```
**Example 1**
```text
Input: parent = [-1, 0, 0, 1, 1, 3, 2], deleted = [1]
Output: 3
```
Nodes 3 and 4 become children of node 0. The longest paths, `0 → 3 → 5` and `0 → 2 → 6`, each have 3 nodes.
**Example 2**
```text
Input: parent = [-1, 0, 0, 1, 1, 3, 2], deleted = [1, 3, 2]
Output: 2
```
Node 5 moves up past the deleted nodes 3 and 1 to node 0, and node 6 moves up to node 0. The root then has children 4, 5 and 6, all leaves.
**Example 3**
```text
Input: parent = [-1, 0, 0, 1, 1, 3, 2], deleted = []
Output: 4
```
Nothing is deleted, and the longest path `0 → 1 → 3 → 5` has 4 nodes.
Overview: Given an N-ary tree as a parent array and a set of nodes to delete, where each deleted node's children are promoted to its nearest surviving ancestor, return the height of the resulting tree. It tests tree traversal over a parent array and careful reasoning about how deletions change depths.
You are given a rooted N-ary tree and a list of nodes to delete. The tree has `n` nodes numbered `0` to `n - 1` and is described by the array `parent`: node `0` is the root and `parent[0] == -1`, and for every other node `i`, `parent[i]` is the index of its parent. Parents can have larger indices than their children.
Deleting a node removes it from the tree, but its children are not removed with it: each child is attached to the deleted node's parent instead. If that parent is deleted too, the children keep moving up until they reach the nearest ancestor that is not deleted. The result does not depend on the order in which the deletions are applied. The root is never deleted.
Implement `height_after_deletions(parent, deleted)`, which returns the height of the tree after every node in `deleted` has been removed. The height is the number of nodes on the longest path from the root down to any node, so a tree that consists of the root alone has height 1. The returned height is at most `n <= 10^5`, so it fits in a 32-bit integer.
### Example 1
```text
Input: parent = [-1, 0, 0, 1, 1, 3, 2], deleted = [1]
Output: 3
```
In this tree node 0 has children 1 and 2, node 1 has children 3 and 4, node 3 has child 5, and node 2 has child 6. Deleting node 1 makes nodes 3 and 4 children of node 0. The longest paths, `0 -> 3 -> 5` and `0 -> 2 -> 6`, each have 3 nodes.
### Example 2
```text
Input: parent = [-1, 0, 0, 1, 1, 3, 2], deleted = [1, 3, 2]
Output: 2
```
Node 5 moves up past the deleted nodes 3 and 1 to node 0, and node 6 moves up to node 0. The root then has children 4, 5 and 6, all leaves, so the height is 2.
### Constraints
- `1 <= n == len(parent) <= 10^5`
- `parent[0] == -1`, and for `i >= 1`, `0 <= parent[i] <= n - 1`; the parent links form a single tree rooted at node `0` with no cycles.
- `0 <= len(deleted) <= n - 1`
- The values in `deleted` are distinct, each between `1` and `n - 1`.
- The tree can be a single path, so its depth can reach `n`.
Constraints
- 1 <= n == len(parent) <= 10^5
- parent[0] == -1, and for i >= 1, 0 <= parent[i] <= n - 1; the parent links form a single tree rooted at node 0 with no cycles.
- 0 <= len(deleted) <= n - 1
- The values in deleted are distinct, each between 1 and n - 1.
- The tree can be a single path, so its depth can reach n.
Examples
Input: ([-1], [])
Expected Output: 1
Explanation: Minimum valid input: the root alone has height 1.
Input: ([-1, 0], [1])
Expected Output: 1
Explanation: Smallest deletion: removing the only child leaves the root alone.
Hints
- A deletion never changes which surviving nodes are ancestors of a surviving node; it only removes nodes from the paths that run through it.
- Parents can have larger indices than their children, so scanning nodes in index order does not guarantee a parent is processed before its child.
- The tree can be a single path of 10^5 nodes, so avoid a traversal whose call depth grows with the tree depth.