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]]

 
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.

Difficulty: interview

Starter code:

# 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[int]) -> List[TreeNode]:
        

Solutions:
# 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[int]) -> List[TreeNode]:
        ans, to_delete = [], set(to_delete)
        def search(root, is_root):
            if not root: return None
            root_deleted = root.val in to_delete
            if is_root and not root_deleted:
                ans.append(root)
            root.left = search(root.left, root_deleted)
            root.right = search(root.right, root_deleted)
            return None if root_deleted else root
        search(root, True)
        return ans

# 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[int]) -> List[TreeNode]:
        ans = []
        to_delete = set(to_delete)
        
        def dfs(node, has_parent):
            if not node: return False
            if node.val not in to_delete and not has_parent:
                    ans.append(node)
            if dfs(node.left, node.val not in to_delete): node.left = None
            if dfs(node.right, node.val not in to_delete): node.right = None
            return  node.val in to_delete
        dfs(root, False)
        return ans

# 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 merge(self, root, left, right):
        replace_left = replace_right = None
        for i in range(len(left)):
            if left[i] == root.left:
                replace_left = i
                
        for i in range(len(right)):
            if right[i] == root.right:
                replace_right = i
                
        if replace_left is not None and replace_right is None:
            left[replace_left] = root
            return left + right
        elif replace_right is not None and replace_left is None:
            right[replace_right] = root
            return left + right
        
        result = (
            [node for node in left if node != root.left] + 
            [node for node in right if node != root.right]
        )
        result.append(root)
        return result
    
    def helper(self, root, to_delete):
        if not root:
            return []
        if not root.left and not root.right:
            if root.val in to_delete:
                return []
            return [root]
        
        left = self.delNodes(root.left, to_delete)
        right = self.delNodes(root.right, to_delete)
        
        if root.left and root.left.val in to_delete:
            root.left = None
            
        if root.right and root.right.val in to_delete:
            root.right = None
        
        if root.val in to_delete:
            return left + right
        
        return self.merge(root, left, right)
            
    def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
        return self.helper(root, set(to_delete))
            
        
            


# 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[int]) -> List[TreeNode]:
        res = []
        def rec(curr, deleted):
            nonlocal res
            if not curr:
                return None
            if curr.val in to_delete:
                curr.left = rec(curr.left, True)
                curr.right = rec(curr.right, True)
                
            else:
                curr.left = rec(curr.left, False)
                curr.right = rec(curr.right, False)
                if deleted:
                    res.append(curr)
            return None if curr.val in to_delete else curr
        rec(root, True)
        return res

# 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[int]) -> List[TreeNode]:
        if root is None: return
        tovisit = []
        result = []
        if root in to_delete:
            if root.left is not None:
                tovisit.append(root.left)
                result.append(root.left)
            if root.right is not None:
                tovisit.append(root.right)
                result.append(root.right)
        else:
            tovisit.append(root)
            result.append(root)
            
        while len(tovisit) > 0:
            new_tovisit = []
            for item in tovisit:
                if item.val in to_delete:
                    if item.left is not None:
                        result.append(item.left)
                    if item.right is not None:
                        result.append(item.right)
                    if item in result:
                        result.remove(item)
                if item.left is not None:
                    new_tovisit.append(item.left)
                    if item.left.val in to_delete:
                        item.left = None
                if item.right is not None:
                    new_tovisit.append(item.right)
                    if item.right.val in to_delete:
                        item.right = None
            tovisit = new_tovisit
        return result

# 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[int]) -> List[TreeNode]:
        roots = []
        
        def deleting(node, to_delete, roots):
            if node == None:
                return
            elif node.val in to_delete:
                if node.left != None:
                    roots.append(node.left)
                if node.right != None:
                    roots.append(node.right)
                    
                try:
                    while True:
                        roots.remove(node)
                except:
                    pass
                    
            
            if node.left != None and node.left.val in to_delete:
                deleting(node.left, to_delete, roots)
                node.left = None
            else:
                deleting(node.left, to_delete, roots)
                
            if node.right != None and node.right.val in to_delete:
                deleting(node.right, to_delete, roots)
                node.right = None
            else:
                deleting(node.right, to_delete, roots)
                
        deleting(root, to_delete, roots)
        if root.val not in to_delete:
            roots.append(root)
            
        return roots

# 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

from queue import Queue

class Solution:
    def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
        if not root:
            return []
        
        deleted = set()
        for node in to_delete:
            deleted.add(node)
        
        out = []
        self.bfs(root, deleted, out)
        return out
        
    def bfs(self, root, deleted, out):
        q = Queue()
        q.put((root, True))
        
        while q.qsize() > 0:
            node, parent_delete = q.get()
            
            if node.val in deleted:
                curr_delete = True
            else:
                curr_delete = False
                
            if node.left:
                q.put((node.left, curr_delete))
                if node.left.val in deleted:
                    node.left = None
                    
            if node.right:
                q.put((node.right, curr_delete))
                if node.right.val in deleted:
                    node.right = None
                                
            if curr_delete:
                node.left = None
                node.right = None
            elif parent_delete:
                out.append(node)            

# 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[int]) -> List[TreeNode]:
        roots = []
        roots.append(root)
        
        def removeRoot(root, roots):
            index = 0
            for i in roots:
                if i == root:
                    roots.pop(index)
                index+=1
                
        def delete(root, prev, roots, to_delete):
            left = root.left
            right = root.right
            if root.val in to_delete:
                removeRoot(root, roots)
                if left:
                    roots.append(root.left)
                if right:
                    roots.append(root.right)
                root.left = None
                root.right = None
                if prev:
                    if prev.left == root:
                        prev.left = None
                    if prev.right == root:
                        prev.right = None
            
            if left:
                delete(left, root, roots, to_delete)
            if right:
                delete(right, root, roots, to_delete)
                
        delete(root, None, roots, to_delete)
        return roots

# 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[int]) -> List[TreeNode]:
        # from collections import deque
        # queue = deque([root])
        # visited = []
        # while queue:
        #     curr = queue.popleft()
        #     if curr:
        #         visited.append(curr)
        #         queue.extend([curr.left, curr.right])
        # res = []
        # for node in visited:
        #     if node.val in to_delete:
        #         if node.left: res.append(node.left)
        #         if node.right: res.append(node.right)
        #         node = None
        # if root and root.val not in to_delete:
        #     res.append(root)
        # return res
        
        stack = [(root, True)]
        res = []
        while stack:
            curr, toBeRoot = stack.pop()
            if curr:
                if curr.val not in to_delete and toBeRoot:
                    res.append(curr)
                toBeRoot = curr.val in to_delete
                stack += [(curr.left,toBeRoot), (curr.right, toBeRoot)]
                if curr.left and curr.left.val in to_delete: curr.left = None
                if curr.right and curr.right.val in to_delete: curr.right = None
                    
        return res

# 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 walk(self, node, to_delete):
        
        if not node:
            return []
        
        roots = []
        
        if node.left:
            roots += self.walk(node.left, to_delete)
            if node.left.val in to_delete:
                node.left = None
            elif node.val in to_delete:
                roots.append(node.left)
                
        if node.right:
            roots += self.walk(node.right, to_delete)
            if node.right.val in to_delete:
                node.right = None
            elif node.val in to_delete:
                roots.append(node.right)
        
        return roots
    
    def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
        
        if not root:
            return None
        
        to_delete = set(to_delete)
                
        roots = self.walk(root, to_delete)
        
        if root.val not in to_delete:
            roots.append(root)
        
        return roots

# 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:
    # APP1: convert to_delete to a set, divide and conquer to get left, right.
    # dfs: 1 return child root, None if child deleted. 
    # 2. check if cur in delete, pass it for recursion call
    # 3 check if child is deleted, delete the link to children
    # Runtime: 98%
    def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
        if not root:
            return []
        res, to_delete = [], set(to_delete)
        self.dfs(root, res, to_delete, True)
        return res
    
    def dfs(self, root, res, to_delete, parent_deleted):
        if not root:
            return None
        if parent_deleted and root.val not in to_delete:
            res.append(root)
            
        root_deleted = True if root.val in to_delete else False
        root.left = self.dfs(root.left, res, to_delete, root_deleted)
        root.right = self.dfs(root.right, res, to_delete, root_deleted)
        return None if root_deleted else root

# 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[int]) -> List[TreeNode]:
        def dfs(root: TreeNode, has_parent: bool) -> TreeNode:
            if not root:
                return 
                
            if root.val in to_delete:
                root.left = dfs(root.left, has_parent=False)
                root.right = dfs(root.right, has_parent=False)
                return
            else:
                if not has_parent:
                    result.append(root)
                root.left = dfs(root.left, has_parent=True)
                root.right = dfs(root.right, has_parent=True)
                return root

        result = []
        dfs(root, has_parent=False)
        return result


# 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[int]) -> List[TreeNode]:

        to_delete = set(to_delete)
        res = []
        def walk(root, parent_exist):
            if root is None:
                return None
            if root.val in to_delete:
                root.left = walk(root.left, parent_exist=False)
                root.right = walk(root.right, parent_exist=False)
                return None
            else:
                if not parent_exist:
                    res.append(root)
                root.left = walk(root.left, parent_exist=True)
                root.right = walk(root.right, parent_exist=True)
                return root
        walk(root, parent_exist=False)
        return res

# 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[int]) -> List[TreeNode]:
        new_roots = []
        def delete_nodes(node, parent_deleted):
            if not node:
                return False
            delete = False
            for value in to_delete:
                if value == node.val:
                    delete = True
            if parent_deleted and not delete:
                new_roots.append(node)
            left, right = delete_nodes(node.left, delete), delete_nodes(node.right, delete)
            if left:
                node.left = None
            if right:
                node.right = None
            return delete
        
        delete_nodes(root, True)
        return new_roots

# 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[int]) -> List[TreeNode]:
        results = []
        def dft(root, to_delete):
            if not root:
                return
            dft(root.left, to_delete) 
            dft(root.right, to_delete)
            if root.left and root.left.val in to_delete:
                root.left = None
            if root.right and root.right.val in to_delete:
                root.right = None 
            if root.val in to_delete:
                print((root.val))
                if root.right:
                    print((root.right.val))
                    results.append(root.right)
                    root.right = None
                if root.left:
                    print((root.left.val))
                    results.append(root.left)
                    root.left = None
           
        dft(root, to_delete)
        if root.val not in to_delete:
            results.append(root) 
        return results
             
            


# 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[int]) -> List[TreeNode]:
        to_delete = set(to_delete)
        ans = []
        def helper(node, isRoot, parent, p_left):
            if isRoot:
                ans.append(node)
                
            if node.val in to_delete:
                if isRoot:
                    ans.pop()
                if parent:
                    if p_left:
                        parent.left = None
                    else:
                        parent.right = None
                if node.left:                    
                    helper(node.left, True, node, True)
                if node.right:                    
                    helper(node.right, True, node, False)
            else:
                if node.left:
                    helper(node.left, False, node, True)
                if node.right:
                    helper(node.right, False, node, False)
                    
            return
        
        helper(root, True, None, None)
        return ans
                    
            
            
            
            
            
            
            
            
            
            
#             if node.val in to_delete:
#                 if node.left:
#                     ans.append(node.left)
#                     helper(node.left)
#                 if node.right:
#                     ans.append(node.right)
#                     helper(node.right)
#                 ans.pop()
#                 to_delete.remove(node.val)
                
#             if node.left and node.left.val in to_delete:
#                 node.left = None
#             if node.right and node.right.val in to_delete:
#                 node.right = None
                
#             return
#         helper(root)
#         return ans


# 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[int]) -> List[TreeNode]:
        self.deletes = set(to_delete)
        self.res = list()
        root = self.helper(root)
        if root:
            self.res.append(root)
        return self.res
    
    def helper(self, root):
        if not root:
            return root
        root.left = self.helper(root.left)
        root.right = self.helper(root.right)
        if root.val in self.deletes:
            if root.left:
                self.res.append(root.left)
            if root.right:
                self.res.append(root.right)
            root = None
        return root

# 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[int]) -> List[TreeNode]:
        if not root:
            return []
        
        res = set([root])
        
        deleteSet = set(to_delete)
        
        def dfs(root):
            
            if not root:
                return
            
            if root.val in deleteSet:
                if root in res:
                    res.remove(root)
                if root.left:
                    res.add(root.left)
                if root.right:
                    res.add(root.right)
            
            dfs(root.left)
            dfs(root.right)
            
            if root.left and root.left.val in deleteSet:
                root.left = None
            if root.right and root.right.val in deleteSet:
                root.right= None
                
            
                
        dfs(root)
        
        return list(res)

# 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 delete(self, root, to_delete, parent, res):
        if not root:
            return root
        else:
            if parent: 
                if root.val in to_delete:
                    root.left = self.delete(root.left, to_delete, False, res)
                    root.right = self.delete(root.right, to_delete, False, res)
                    return None
                else:
                    root.left = self.delete(root.left, to_delete, True, res)
                    root.right = self.delete(root.right, to_delete, True, res)
                    return root
            else:
                if root.val in to_delete:
                    root.left = self.delete(root.left, to_delete, False, res)
                    root.right = self.delete(root.right, to_delete, False, res)
                    return None
                else:
                    res.append(root)
                    root.left = self.delete(root.left, to_delete, True, res)
                    root.right = self.delete(root.right, to_delete, True, res)
                    return root
                
        
    def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
        res = []
        root = self.delete(root, set(to_delete), False, res)
        return res


# 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[int]) -> List[TreeNode]:
        ret = []
        def dfs(node, parent):
            if node:
                if node.val in to_delete:
                    node.left=dfs(node.left, False)
                    node.right=dfs(node.right, False)
                else:
                    if not parent:
                        ret.append(node)
                    node.left=dfs(node.left, True)
                    node.right=dfs(node.right, True)
                    return node
        dfs(root, False)
        return ret

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

class Solution(object):
    def delNodes(self, root, to_delete):
        \"\"\"
        :type root: TreeNode
        :type to_delete: List[int]
        :rtype: List[TreeNode]
        \"\"\"
        if not root:
            return root
        res = []
        self.dfs(root, to_delete, res)
        if root.val not in to_delete:
            res.append(root)
        return res
    
    def dfs(self, root, to_delete, res):
        if not root:
            return
        root.left = self.dfs(root.left, to_delete, res)
        root.right = self.dfs(root.right, to_delete, res)
        if root.val in to_delete:
            if root.left:
                res.append(root.left)
            if root.right:
                res.append(root.right)
            return None
        return root

class Solution:
    def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
        final_list = []
        def rec(node):
            if node == None:
                return None
            node.left = rec(node.left)
            node.right = rec(node.right)
            if node.val in to_delete:
                if node.left!= None:
                    final_list.append(node.left)
                if node.right!= None:
                    final_list.append(node.right)
                return None
            return node
        rec(root)
        if root.val not in to_delete:
            final_list.append(root)
        return(final_list)


# 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[int]) -> List[TreeNode]:
        output = []
        stack = [(0, root)]
        # delete_set = set(to_delete)
        
        def stackChildren(level, node):
            if node.right:
                stack.append((level, node.right))
                if level > 0 and node.right.val in to_delete:
                    node.right = None
            if node.left:
                stack.append((level, node.left))
                if level > 0 and node.left.val in to_delete:
                    node.left = None
            
        while stack:
            level, node = stack.pop()
            if node.val in to_delete:
                # delete_set.remove(node.val)
                stackChildren(0, node)
            else:
                if level == 0:
                    output.append(node)
                stackChildren(level+1, node)
                
        return output