Katkat
Back

Height of an N-ary Tree After Deleting Nodes and Promoting Their Children

SnowflakeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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 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

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:

parent = [-1, 0, 0, 1, 1, 3, 2]

 0
 / \
 1 2
 / \ \
 3 4 6
 |
 5

Example 1

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

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

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.