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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Delete Nodes And Return Forest

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem involves a binary tree and requires deletion of specific nodes.
  • After deletion, any child nodes of the deleted nodes must be preserved as separate trees in the forest.
  • A depth-first search (DFS) approach is suitable for traversing the tree and handling deletions.
  • A set can be used for quick look-up of nodes to delete.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree. Each node is processed once. Space Complexity: O(H), where H is the height of the tree due to the recursion stack. Additionally, O(K) for the set of nodes to delete.

Solution

The solution uses a depth-first search (DFS) approach to traverse the binary tree. For each node, we check if it is in the to_delete set. If it is, we recursively delete it and add its non-null children to the result list as new roots of trees in the forest. If it is not in to_delete, we keep it and potentially add it to the result list if its parent was deleted. This process ensures that all relevant nodes are handled appropriately in the resulting forest.

Code Solutions

def delNodes(root, to_delete):
    def dfs(node):
        if not node:
            return None
        if node.val in to_delete_set:
            # If the current node is to be deleted, we do not add it to the result
            if node.left:
                dfs(node.left)
            if node.right:
                dfs(node.right)
            return None  # Return None to indicate this node is deleted
        else:
            # If not deleted, we may add it as a root if it has no deleted parent
            if not parent_deleted:
                result.append(node)
            # Continue DFS on children
            node.left = dfs(node.left)
            node.right = dfs(node.right)
            return node
    
    to_delete_set = set(to_delete)
    result = []
    dfs(root)
    return result
← Back to All Questions