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

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

Given a binary tree whose node values are all distinct, and a list of values to delete, remove every node whose value is in the list. Removing a node cuts the link from its parent and the links to its children, so each child of a removed node that is not itself removed becomes the root of a separate tree. Return the forest of trees that remain. ### Function Signature ```python def split_into_forest(tree: list[int | None], to_delete: list[int]) -> list[list[int | None]]: ``` ### Rules - `tree` is the level-order (breadth-first, left to right) listing of the nodes. Each existing node's two child slots appear in order, with `None` for a missing child; a missing node has no child slots. Trailing `None` entries may be omitted. `tree[0]` is the root and is never `None`. - Values in `to_delete` that do not occur in the tree are ignored. - Return each remaining tree in the same level-order format, with every trailing `None` removed. - Order the returned trees by their root values, smallest first. If every node is deleted, return an empty list. ### 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 **Example 1** ```text Input: tree = [1, 2, 3, 4, 5, 6, 7], to_delete = [3, 5] Output: [[1, 2, None, 4], [6], [7]] ``` ```text 1 / \ 2 3 / \ / \ 4 5 6 7 ``` Deleting 3 leaves its children 6 and 7 as single-node trees. Deleting 5 removes the right child of 2, so the tree rooted at 1 keeps 2 as its left child and 4 as the left child of 2. **Example 2** ```text Input: tree = [1, 2, 4, None, 3], to_delete = [3] Output: [[1, 2, 4]] ``` Node 3 is the right child of 2. Removing it leaves one tree with root 1 and children 2 and 4. **Example 3** ```text Input: tree = [5, 3, 8, None, 4], to_delete = [5, 9] Output: [[3, None, 4], [8]] ``` Deleting the root leaves two trees, rooted at 3 and 8. Node 4 stays the right child of 3, and 9 does not occur in the tree.

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.

You are given a binary tree whose node values are all distinct, and a list `to_delete` of values. Remove every node whose value is in `to_delete`. Removing a node cuts the link from its parent and the links to its children, so each child of a removed node that is not itself removed becomes the root of a separate tree. Return the forest of trees that remain. Implement `split_into_forest(tree, to_delete)`. ### Input - `tree` is the level-order (breadth-first, left to right) listing of the nodes. Each existing node's two child slots appear in order, with `None` for a missing child; a missing node has no child slots. Trailing `None` entries may be omitted. `tree[0]` is the root and is never `None`. - `to_delete` lists the values to remove. Values in `to_delete` that do not occur in the tree are ignored. `None` is `null` in JavaScript and Java and `std::nullopt` in C++. ### Output - Return each remaining tree in the same level-order format, with every trailing `None` removed. - Order the returned trees by their root values, smallest first. - If every node is deleted, return an empty list. Every value is at most 10^5, so no value exceeds 2^31 - 1; 32-bit integers suffice in every language. ### Example 1 ```text Input: tree = [1, 2, 3, 4, 5, 6, 7], to_delete = [3, 5] Output: [[1, 2, None, 4], [6], [7]] ``` ```text 1 / \ 2 3 / \ / \ 4 5 6 7 ``` Deleting 3 leaves its children 6 and 7 as single-node trees. Deleting 5 removes the right child of 2, so the tree rooted at 1 keeps 2 as its left child and 4 as the left child of 2. ### Example 2 ```text Input: tree = [5, 3, 8, None, 4], to_delete = [5, 9] Output: [[3, None, 4], [8]] ``` Deleting the root leaves two trees, rooted at 3 and 8. Node 4 stays the right child of 3, and 9 does not occur in the tree. ### 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.

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

  1. 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.
  2. 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.
  3. When writing a remaining tree back out, treat a deleted child exactly like a missing child, then drop the trailing None entries.

Delete Nodes and Return the Sorted Forest

mediumGoogleSoftware Engineer

You are given a binary tree whose node values are all distinct, and a list to_delete of values. Remove every node whose value is in to_delete. Removing a node cuts the link from its parent and the links to its children, so each child of a removed node that is not itself removed becomes the root of a separate tree. Return the forest of trees that remain.

Implement split_into_forest(tree, to_delete).

Input

  • tree is the level-order (breadth-first, left to right) listing of the nodes. Each existing node's two child slots appear in order, with None for a missing child; a missing node has no child slots. Trailing None entries may be omitted. tree[0] is the root and is never None.
  • to_delete lists the values to remove. Values in to_delete that do not occur in the tree are ignored.

None is null in JavaScript and Java and std::nullopt in C++.

Output

  • Return each remaining tree in the same level-order format, with every trailing None removed.
  • Order the returned trees by their root values, smallest first.
  • If every node is deleted, return an empty list.

Every value is at most 10^5, so no value exceeds 2^31 - 1; 32-bit integers suffice in every language.

Example 1

Input:  tree = [1, 2, 3, 4, 5, 6, 7], to_delete = [3, 5]
Output: [[1, 2, None, 4], [6], [7]]
        1
       / \
      2   3
     / \ / \
    4  5 6  7

Deleting 3 leaves its children 6 and 7 as single-node trees. Deleting 5 removes the right child of 2, so the tree rooted at 1 keeps 2 as its left child and 4 as the left child of 2.

Example 2

Input:  tree = [5, 3, 8, None, 4], to_delete = [5, 9]
Output: [[3, None, 4], [8]]

Deleting the root leaves two trees, rooted at 3 and 8. Node 4 stays the right child of 3, and 9 does not occur in the tree.

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

Example 1
Input
([1, 2, 3, 4, 5, 6, 7], [3, 5])
Output
[[1, 2, None, 4], [6], [7]]
Notes
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.
Example 2
Input
([1, 2, 4, None, 3], [3])
Output
[[1, 2, 4]]
Notes
Source example 2: 3 is the right child of 2; after deleting it only trailing None slots remain, and they are trimmed.

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.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def split_into_forest(tree: list[int | None], to_delete: list[int]) -> list[list[int | None]]:
Sample call
split_into_forest([1, 2, 3, 4, 5, 6, 7], [3, 5])
Language
Case 1
Input
([1, 2, 3, 4, 5, 6, 7], [3, 5])
Expected
[[1, 2, None, 4], [6], [7]]
Case 2
Input
([1, 2, 4, None, 3], [3])
Expected
[[1, 2, 4]]

Browse More Questions

Show the approach

Approach

Rebuild the tree from the level-order list with a FIFO queue: each dequeued node consumes the next two entries as its left and right child slots, a None entry creates no node, and parsing stops when the list runs out, so omitted and explicit trailing None entries parse identically. Mark a node as gone when its value is in a hash set built from to_delete; values that do not occur in the tree never match a node and are ignored. A surviving node is the root of a remaining tree exactly when it has no surviving parent: it is the original root, or its parent is gone. Every surviving node belongs to exactly one remaining tree (walk up through surviving parents until the walk stops at such a root), so these roots enumerate the forest without duplicates. Sort the roots by value; values are distinct, so the order is total. For each root, run a breadth-first walk over surviving nodes only: each dequeued node emits its left then right child value, or None when that child is missing or deleted. Because only existing nodes emit child slots, this reproduces the level-order format exactly; finally strip the trailing None entries. Edge cases: deleting the root, deleting a parent together with its child (the child is not promoted, but its surviving children are), deleting every node (empty list), sparse inputs where index arithmetic such as 2i+1 would misplace nodes, and skewed trees of height up to 10^4, which is why every traversal is iterative rather than recursive.

Time complexity:
O(n log n + d)
Space complexity:
O(n + d)