Katkat
Back

Compute height of tree with deleted nodes; minimize deletions

SnowflakeSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates understanding of tree data structures, connectivity after node deletions, and optimization for minimizing additional removals, and is categorized under Coding & Algorithms. It is commonly asked to assess reasoning about tree pruning and height computation under constraints, testing both conceptual understanding of tree properties and practical algorithmic implementation.

You are given a rooted tree (not necessarily binary). Each node has a list of children. Some nodes are marked as deleted = true.

Define the effective tree as the tree after removing every deleted node and all edges incident to it; nodes that become disconnected from the root are not counted.

  1. Compute the height of the effective tree (maximum number of nodes on any root-to-leaf path in the effective tree; if the root is deleted, the height is 0).

  2. Follow-up: Given an integer K, delete the minimum number of additional nodes (you may choose any nodes to delete) so that the height of the effective tree is at most K. Return that minimum number of additional deletions.

Clarify in your solution what “deleting a node” means (assume a deleted node is removed and you cannot traverse through it from the root).