We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Delete Nodes And Return Forest

Number: 1207

Difficulty: Medium

Paid? No

Companies: Google, Meta, Amazon

Problem Description

Given the root of a binary tree with distinct node values, delete all nodes whose values are found in the list to_delete. After deletion, the remaining nodes form a forest (a collection of disjoint trees). Return the root nodes of each tree in the forest. The result can be returned in any order.

Key Insights

  • Use a recursive depth-first search (DFS) to traverse the tree.
  • At each node, determine if it should be deleted based on the to_delete set.
  • When deleting a node, ensure that its non-deleted children are added as new roots in the forest.
  • Postorder traversal (processing children before the current node) is beneficial so that children are processed before potentially deleting the parent.
  • Using a set for to_delete items allows for fast lookup.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes since each node is visited once. Space Complexity: O(N) for the recursion stack and the set used to store deletion values and resulting forest.

Solution

We employ a DFS approach to traverse the tree in a postorder manner, processing left and right children first. For each node:

  • Check if the node should be deleted by looking it up in the to_delete set.
  • If the node is flagged for deletion, add its non-null children as potential new roots to the forest.
  • Return null for a deleted node and the node itself if it is kept. This recursive process ensures that any subtree whose root gets deleted properly adds any potential subtrees to the answer list before the node is removed.

Code Solutions

# Python solution with line-by-line comments

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def delNodes(self, root: TreeNode, to_delete: list) -> list:
        # Convert the to_delete list to a set for faster lookup
        to_delete_set = set(to_delete)
        # Result list to hold roots of the remaining forest
        remaining_forest = []
        
        def dfs(node, is_root):
            # Base condition: if the current node is null, return None
            if not node:
                return None
            
            # Determine if current node needs deletion
            node_deleted = node.val in to_delete_set
            
            # If this node is a root (or newly added) and is not deleted,
            # add it to the remaining forest.
            if is_root and not node_deleted:
                remaining_forest.append(node)
            
            # Recursively process the left and right subtrees
            node.left = dfs(node.left, node_deleted)
            node.right = dfs(node.right, node_deleted)
            
            # Return None if node is deleted, else return the node itself.
            return None if node_deleted else node
        
        # Start DFS from the root, the root is considered as a starting root.
        dfs(root, True)
        return remaining_forest
← Back to All Questions