Compute height after deletions; enumerate valid delete sets
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Quick Answer: 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.
Part 1: Height After Deletions with Child Promotion
Constraints
- 0 <= number of nodes <= 100000
- Node ids are unique positive integers.
- root_id is -1 if and only if the tree is empty.
- Every non-missing child id appears as a key in nodes.
- The input graph is a valid rooted binary tree with no cycles.
- delete_ids contains valid node ids from the tree.
Examples
Input: (-1, {}, [])
Expected Output: 0
Explanation: The tree is empty, so the resulting forest is empty.
Input: (10, {10: [-1, -1]}, [10])
Expected Output: 0
Explanation: The only node is deleted, leaving an empty forest.
Input: (1, {1: [2, 3], 2: [4, 5], 3: [-1, 6], 4: [-1, -1], 5: [-1, -1], 6: [-1, -1]}, [2])
Expected Output: 3
Explanation: Deleting node 2 promotes nodes 4 and 5, but the path 1 -> 3 -> 6 still has 3 levels.
Input: (1, {1: [2, 3], 2: [4, 5], 3: [-1, 6], 4: [-1, -1], 5: [-1, -1], 6: [-1, -1]}, [1])
Expected Output: 2
Explanation: Deleting the root creates a forest rooted at promoted children. The tallest component has height 2.
Input: (1, {1: [2, 3], 2: [4, 5], 3: [-1, 6], 4: [-1, -1], 5: [-1, -1], 6: [-1, -1]}, [2, 3])
Expected Output: 2
Explanation: Nodes 2 and 3 are removed, so the deepest remaining paths from node 1 have 2 levels.
Solution
def solution(root_id, nodes, delete_ids):
deleted = set(delete_ids)
if root_id == -1:
return 0
# Postorder traversal without recursion, so skewed trees are safe.
heights = {-1: 0}
stack = [(root_id, False)]
while stack:
node, visited = stack.pop()
if node == -1:
continue
if visited:
left, right = nodes[node]
best_child_height = max(heights.get(left, 0), heights.get(right, 0))
if node in deleted:
# Deleted nodes do not count as a level; their children are promoted.
heights[node] = best_child_height
else:
heights[node] = 1 + best_child_height
else:
stack.append((node, True))
left, right = nodes[node]
if right != -1:
stack.append((right, False))
if left != -1:
stack.append((left, False))
return heights[root_id]Time complexity: O(N + D), where N is the number of nodes and D is the number of ids in delete_ids.. Space complexity: O(N + D), for the height table, traversal stack, and deletion set..
Hints
- For height, you do not need to explicitly rebuild the promoted tree.
- A deleted node contributes 0 levels but passes upward the maximum height of its children.
Part 2: Enumerate Deletion Sets Producing a Target Height
Constraints
- 0 <= number of nodes <= 18
- 0 <= max_deletions <= number of nodes
- 0 <= target_height <= number of nodes
- Node ids are unique positive integers.
- root_id is -1 if and only if the tree is empty.
- Every non-missing child id appears as a key in nodes.
- The input graph is a valid rooted binary tree with no cycles.
Examples
Input: (-1, {}, 3, 0)
Expected Output: [[]]
Explanation: The empty deletion set leaves an empty forest with height 0.
Input: (7, {7: [-1, -1]}, 1, 0)
Expected Output: [[7]]
Explanation: Deleting the only node is the only way to get height 0.
Input: (1, {1: [2, 3], 2: [4, 5], 3: [-1, 6], 4: [-1, -1], 5: [-1, -1], 6: [-1, -1]}, 0, 3)
Expected Output: [[]]
Explanation: No deletions are allowed, and the original tree already has height 3.
Input: (1, {1: [2, 3], 2: [4, 5], 3: [-1, 6], 4: [-1, -1], 5: [-1, -1], 6: [-1, -1]}, 1, 2)
Expected Output: [[1]]
Explanation: With one deletion, only deleting the root reduces the maximum height from 3 to exactly 2.
Input: (1, {1: [2, 3], 2: [4, 5], 3: [-1, 6], 4: [-1, -1], 5: [-1, -1], 6: [-1, -1]}, 2, 2)
Expected Output: [[1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 3], [2, 6]]
Explanation: These are exactly the deletion sets of size at most 2 that hit every original 3-level path while leaving at least one 2-level path.
Solution
def solution(root_id, nodes, max_deletions, target_height):
from itertools import combinations
ids = sorted(nodes.keys())
limit = min(max_deletions, len(ids))
def compute_height(deleted):
if root_id == -1:
return 0
heights = {-1: 0}
stack = [(root_id, False)]
while stack:
node, visited = stack.pop()
if node == -1:
continue
if visited:
left, right = nodes[node]
best_child_height = max(heights.get(left, 0), heights.get(right, 0))
if node in deleted:
heights[node] = best_child_height
else:
heights[node] = 1 + best_child_height
else:
stack.append((node, True))
left, right = nodes[node]
if right != -1:
stack.append((right, False))
if left != -1:
stack.append((left, False))
return heights[root_id]
answer = []
# Generate combinations directly, so each set appears once.
for size in range(limit + 1):
for combo in combinations(ids, size):
deleted = set(combo)
if compute_height(deleted) == target_height:
answer.append(list(combo))
answer.sort()
return answerTime complexity: O(M * S + output_size), where M is the number of nodes and S = sum(C(M, i) for i = 0..min(max_deletions, M)) candidate deletion sets.. Space complexity: O(M + output_size), excluding the returned output contents this uses O(M) auxiliary space per height computation..
Hints
- Sort node ids first and generate combinations, not permutations, to avoid duplicate deletion sets.
- For each candidate set, compute height using the same contracted-node recurrence from Part 1.