N-ary Tree Height After Deleting Nodes and Reattaching Their Children
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. You are given the tree as a parent array, together with a list of nodes to delete.
When a node is deleted, its children are attached to the deleted node's parent. If that parent is deleted as well, the children move up again, so in the end every remaining node hangs directly under its nearest ancestor that is not deleted.
Return the height of the tree that remains after all the deletions.
### Function Signature
```python
def height_after_deletions(parent: list[int], deleted: list[int]) -> int:
```
`parent[i]` is the parent of node `i`, and `parent[0] == -1`. `deleted` lists the nodes to delete.
### 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 is never deleted.
- Apart from the reattachment described above, the tree does not change. The remaining tree, and therefore the answer, does not depend on the order of `deleted`.
### 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.
- `0 <= len(deleted) <= len(parent) - 1`. The entries of `deleted` are distinct, and each lies between `1` and `len(parent) - 1`.
- The tree may be a single path of `10^5` nodes.
### Examples
**Example 1**
```text
Input: parent = [-1, 0, 0, 1, 1, 3, 2], deleted = [3]
Output: 3
```
The tree has the edges 0 → 1, 0 → 2, 1 → 3, 1 → 4, 3 → 5 and 2 → 6, and its longest path, 0 → 1 → 3 → 5, has 4 nodes. Deleting node 3 attaches node 5 to node 1, so every path now has at most 3 nodes.
**Example 2**
```text
Input: parent = [-1, 0, 1, 2, 3], deleted = [3, 2]
Output: 3
```
The tree is the path 0 → 1 → 2 → 3 → 4. Node 4 belonged to node 3, whose parent, node 2, is also deleted, so node 4 ends up under node 1. The remaining tree is 0 → 1 → 4.
**Example 3**
```text
Input: parent = [-1, 3, 0, 2, 1], deleted = [2]
Output: 4
```
The tree is the path 0 → 2 → 3 → 1 → 4. Deleting node 2 attaches node 3 to the root, leaving 0 → 3 → 1 → 4.
Overview: Given an N-ary tree as a parent array and a set of nodes to delete, move each deleted node's children up to its nearest surviving ancestor and report the height of the resulting tree. Tests building a tree from parent links, reasoning about cascading deletions, and computing depths on a tree that can be a path of 100,000 nodes.
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. The tree is given as an integer array `parent`, where `parent[i]` is the parent of node `i` and `parent[0] == -1`. You are also given a list `deleted` of nodes to delete.
When a node is deleted, its children are attached to the deleted node's parent. If that parent is deleted as well, the children move up again, so in the end every remaining node hangs directly under its nearest ancestor that is not deleted. The root is never deleted. Apart from this reattachment the tree does not change, so the remaining tree, and therefore the answer, does not depend on the order of `deleted`.
Implement `height_after_deletions(parent, deleted)` and return the height of the tree that remains after all the deletions. 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.
**Example 1**
```text
Input: parent = [-1, 0, 0, 1, 1, 3, 2], deleted = [3]
Output: 3
```
The tree has the edges 0 → 1, 0 → 2, 1 → 3, 1 → 4, 3 → 5 and 2 → 6, and its longest path, 0 → 1 → 3 → 5, has 4 nodes. Deleting node 3 attaches node 5 to node 1, so every path now has at most 3 nodes.
**Example 2**
```text
Input: parent = [-1, 0, 1, 2, 3], deleted = [3, 2]
Output: 3
```
The tree is the path 0 → 1 → 2 → 3 → 4. Node 4 belonged to node 3, whose parent, node 2, is also deleted, so node 4 ends up under node 1. The remaining tree is 0 → 1 → 4.
**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.
- `0 <= len(deleted) <= len(parent) - 1`. The entries of `deleted` are distinct, and each lies between `1` and `len(parent) - 1`.
- The tree may be a single path of `10^5` nodes.
The answer is an integer between 1 and `len(parent)` (at most 10^5), so it never exceeds 2^31 - 1; a 32-bit `int` is enough in Java and C++.
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.
- `0 <= len(deleted) <= len(parent) - 1`. The entries of `deleted` are distinct, and each lies between `1` and `len(parent) - 1`.
- The tree may be a single path of `10^5` nodes.
Examples
Input: ([-1], [])
Expected Output: 1
Explanation: Single-node tree with no deletions: the root alone has height 1.
Input: ([-1, 0, 0, 1, 1, 3, 2], [3])
Expected Output: 3
Explanation: Source Example 1: deleting node 3 moves node 5 under node 1, so the longest path drops from 4 to 3 nodes.
Hints
- A remaining node ends up directly under its nearest ancestor that is not deleted. Which nodes from its original root-to-node path are still above it in the final tree?
- The height is decided by the deepest remaining node, so it is enough to know how deep each remaining node sits in the final tree.
- Node numbers need not follow the tree order (a parent may have a larger number than its child), and the tree can be a single path of 10^5 nodes, so plan your traversal order and recursion depth accordingly.