Is Delete Nodes And Return Forest easy or hard?

Delete Nodes And Return Forest is rated Medium difficulty. The challenge comes from correctly updating parent-child relationships while traversing the tree and ensuring that new roots are added to the forest at the right time.

Delete Nodes And Return Forest Python/Java solution

Python and Java implementations typically use a hash set for the delete list and perform a DFS traversal. The recursive function returns the updated subtree after removing nodes and collects new roots whenever a deleted node exposes surviving children.

How to solve Delete Nodes And Return Forest in O(n)?

Store all values to delete in a hash set and traverse the tree once. Using post-order DFS, process children before the parent so you know whether they remain attached. When a node must be deleted, add its non-null children to the forest and return null to remove the node. This single traversal keeps the complexity at O(n).

What is the best approach for Delete Nodes And Return Forest?

Post-order DFS is the most efficient and clean approach. Traverse the binary tree bottom-up, check whether each node should be deleted using a hash set, and detach nodes while promoting valid children as new roots. This approach runs in O(n) time and uses O(h) recursion space.

Is Delete Nodes And Return Forest asked at Google/Amazon/Meta?

Binary tree modification problems like Delete Nodes And Return Forest frequently appear in interviews at large tech companies including Google, Amazon, and Meta. The question tests DFS traversal, tree restructuring, and efficient use of hash sets for constant-time lookups.

What data structure is used in Delete Nodes And Return Forest?

The solution relies on a binary tree structure combined with a hash set for fast membership checks. Depth-First Search or Breadth-First Search traverses the tree while the hash set stores values that must be deleted.

What is the time complexity of Delete Nodes And Return Forest?

The optimal solutions run in O(n) time where n is the number of nodes in the tree. Each node is visited exactly once, and checking whether a node should be deleted takes O(1) time using a hash set. Space complexity is O(h) for DFS recursion or O(n) for BFS traversal.

Description Solution Video 14:48

1110. Delete Nodes And Return Forest

Medium72.4% acceptance4 companies

Given the root of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest. You may return the result in any order.

Example 1:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

Example 2:

Input: root = [1,2,4,null,3], to_delete = [3]
Output: [[1,2,4]]

Constraints:

The number of nodes in the given tree is at most 1000.
Each node has a distinct value between 1 and 1000.
to_delete.length <= 1000
to_delete contains distinct values between 1 and 1000.

Asked at 4 companies

Google Meta Amazon

Topics

14:48

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

1110. Delete Nodes And Return Forest

Asked at 4 companies

Topics

Similar problems