Compute height after deletions; enumerate valid delete sets

Q: Compute height after deletions; enumerate valid delete sets

This is a Coding & Algorithms interview question from Snowflake for Software Engineer roles. View the full question and solution on PracHub.

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

Comments (0)