Compute height after deletions; enumerate valid delete sets

Q: Compute height after deletions; enumerate valid delete sets

This question evaluates competence in binary tree manipulation and combinatorial search, covering promotion-based node deletion, height computation across forest components after root deletion, enumeration of deletion sets with deduplication, pruning strategies, and time/space complexity analysis.

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

Warm-up: You are given a rooted binary tree with unique node ids and a list of ids to delete. When a node is deleted, promote all of its children to become children of the deleted node’s parent (preserving left/right positions when possible; if only one child exists, it occupies the appropriate side). After applying all deletions, compute the number of levels in the resulting tree. State and handle the case where the root is deleted (e.g., produce a forest and return the maximum height across the components) and analyze time/space complexity. Main: With the same promotion rule, you are given a rooted binary tree, an integer n (maximum deletions allowed), and a target height k. Return all unique sets of node ids whose deletion yields a tree whose height is exactly k using at most n deletions. Output each set as a sorted list of ids; avoid duplicates. Describe your search/pruning strategy, correctness argument, and complexity.

Compute height after deletions; enumerate valid delete sets

Overview

Comments (0)