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.

Source: leetcode | Difficulty: MEDIUM
Tags: Tree algorithms

Graph traversal

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


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


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


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


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


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


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)


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


class Solution:

	def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
		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


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


class Solution:

	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


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


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


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


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


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


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


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)


class Solution:

	def delete(self, root, to_delete, parent, res):
		if not root:
			return root
		elif 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
		elif 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


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


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


class Solution:

	def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
		output = []
		stack = [(0, root)]

		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:
				stackChildren(0, node)
			else:
				if level == 0:
					output.append(node)
				stackChildren(level + 1, node)
		return output