Find Tree Height After Deleting Nodes and Promoting Children
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Delete selected nodes from a rooted multiway tree. Deleting a node promotes all of its children to its parent; it does not delete the descendants. Return the final tree height measured in nodes along the longest root-to-leaf path.
Implement `height_after_deletions(parent: int[], deleted: int[]) -> int`.
### Constraints & Assumptions
- The tree has `1 <= n <= 200000` nodes with unique IDs `0..n-1`. Node 0 is the root, `parent[0] == -1`, and each other entry identifies its parent. This array is a practice representation of the source's unique node values.
- The parent array describes a valid tree but parent IDs need not be smaller than child IDs.
- Every deleted ID is a non-root node. Duplicate deleted IDs have no extra effect.
- Any number of non-root nodes may be deleted. A root-only result has height 1.
- Only the height is required; do not construct a rewritten tree merely to return it.
- Aim for O(n + len(deleted)) time. Account for traversal depth when choosing recursive or iterative code.
### Examples
```text
parent = [-1,0,0,2,2,4], deleted = [2]
result = 3
```
The retained path `0 -> 4 -> 5` has three nodes after node 2's children are promoted.
```text
parent = [-1,0,1,2], deleted = [1,2]
result = 2
```
Explain why deleting an internal node reduces the contribution of that node but preserves the descendants' contribution. Include tests for the root-only tree, no deletions, consecutive deleted ancestors, and all non-root nodes deleted, and state time and space complexity.
```hint Count retained nodes on original paths
Promotion changes edges, but the surviving order of nodes along an original root-to-leaf path is unchanged.
```
Overview: Compute tree height after deleting nodes while promoting their children, preserving descendants and counting retained nodes without rebuilding the tree.
Read the full Snowflake Software Engineer interview experience this question came from
Delete selected nodes from a rooted multiway tree. Deleting a node promotes all of its children to its parent; it does not delete the descendants. Return the final tree height measured in nodes along the longest root-to-leaf path.
Implement `height_after_deletions(parent: int[], deleted: int[]) -> int`.
### Constraints & Assumptions
- The tree has `1 <= n <= 200000` nodes with unique IDs `0..n-1`. Node 0 is the root, `parent[0] == -1`, and each other entry identifies its parent. This array is a practice representation of the source's unique node values.
- The parent array describes a valid tree but parent IDs need not be smaller than child IDs.
- Every deleted ID is a non-root node. Duplicate deleted IDs have no extra effect.
- Any number of non-root nodes may be deleted. A root-only result has height 1.
- Only the height is required; do not construct a rewritten tree merely to return it.
- Aim for O(n + len(deleted)) time. Account for traversal depth when choosing recursive or iterative code.
### Examples
```text
parent = [-1,0,0,2,2,4], deleted = [2]
result = 3
```
The retained path `0 -> 4 -> 5` has three nodes after node 2's children are promoted.
```text
parent = [-1,0,1,2], deleted = [1,2]
result = 2
```
Explain why deleting an internal node reduces the contribution of that node but preserves the descendants' contribution. Include tests for the root-only tree, no deletions, consecutive deleted ancestors, and all non-root nodes deleted, and state time and space complexity.
```hint Count retained nodes on original paths
Promotion changes edges, but the surviving order of nodes along an original root-to-leaf path is unchanged.
```
Constraints
- 1 <= n <= 200000; parent describes a valid tree with root 0 and parent[0] == -1.
- Node IDs range from 0 through n-1; parent IDs need not be smaller than children.
- Deleted IDs are nonroot nodes; duplicates have no additional effect and the list has no separate stated length bound.
- Deletion promotes children and preserves descendants. Return longest retained root-to-leaf path length in nodes.
- The root always survives, so a root-only result has height 1.
Examples
Input: ([-1, 0, 0, 2, 2, 4], [2])
Expected Output: 3
Explanation: Deleting node two preserves the retained path 0,4,5.
Input: ([-1, 0, 1, 2], [1, 2])
Expected Output: 2
Explanation: Consecutive deleted ancestors contribute zero while their descendant survives.