Compute height of tree with deleted nodes; minimize deletions

Q: Compute height of tree with deleted nodes; minimize deletions

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

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

Compute height of tree with deleted nodes; minimize deletions

Quick Overview

Comments (0)