Split a Binary Tree into a Forest by Removing Nodes with Given Values
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Overview: Google new-grad onsite coding problem: remove every binary tree node whose value appears in a deletion list and return the forest of trees that remain, each serialized in level order and sorted by root value. Tests tree traversal and correctly re-rooting the children of deleted nodes.
Constraints
- 1 <= number of nodes <= 10^4
- Node values are distinct integers with 1 <= value <= 10^5.
- 0 <= len(to_delete) <= 10^4; the values in to_delete are distinct integers in [1, 10^5].
- The tree is not necessarily balanced; its height can be as large as the number of nodes.
Examples
Input: ([1, 2, 3, 4, 5, 6, 7], [3, 5])
Expected Output: [[1, 2, None, 4], [6], [7]]
Explanation: Source example 1: deleting 3 frees 6 and 7 as single-node trees; deleting 5 (right child of 2) leaves an interior None after 2 and trims the trailing slots.
Input: ([1, 2, 4, None, 3], [3])
Expected Output: [[1, 2, 4]]
Explanation: Source example 2: 3 is the right child of 2; after deleting it only trailing None slots remain, and they are trimmed.
Hints
- A node that survives starts a new tree exactly when it has no surviving parent: either it is the original root or its parent was deleted.
- Recover each node's left and right child from the level-order list first; a missing node contributes no child slots, so positions do not follow a fixed index formula.
- When writing a remaining tree back out, treat a deleted child exactly like a missing child, then drop the trailing None entries.