1110. Delete Nodes And Return Forest LeetCode Solution

In this guide, you will get 1110. Delete Nodes And Return Forest LeetCode Solution with the best time and space complexity. The solution to Delete Nodes And Return Forest problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Delete Nodes And Return Forest solution in C++
Delete Nodes And Return Forest solution in Java
Delete Nodes And Return Forest solution in Python
Additional Resources

1110. Delete Nodes And Return Forest LeetCode Solution image

Problem Statement of Delete Nodes And Return Forest

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.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(\texttt{h} + |\texttt{toDelete}|)

1110. Delete Nodes And Return Forest LeetCode Solution in C++

class Solution {
 public:
  vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
    vector<TreeNode*> ans;
    dfs(root, {to_delete.begin(), to_delete.end()}, true, ans);
    return ans;
  }

 private:
  TreeNode* dfs(TreeNode*& root, const unordered_set<int>&& toDeleteSet,
                bool isRoot, vector<TreeNode*>& ans) {
    if (root == nullptr)
      return nullptr;

    const bool deleted = toDeleteSet.contains(root->val);
    if (isRoot && !deleted)
      ans.push_back(root);

    // If root is deleted, both children have the possibility to be a new root
    root->left = dfs(root->left, std::move(toDeleteSet), deleted, ans);
    root->right = dfs(root->right, std::move(toDeleteSet), deleted, ans);
    return deleted ? nullptr : root;
  }
};
/* code provided by PROGIEZ */

1110. Delete Nodes And Return Forest LeetCode Solution in Java

class Solution {
  public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
    List<TreeNode> ans = new ArrayList<>();
    Set<Integer> toDeleteSet = Arrays.stream(to_delete).boxed().collect(Collectors.toSet());
    dfs(root, toDeleteSet, true, ans);
    return ans;
  }

  private TreeNode dfs(TreeNode root, Set<Integer> toDeleteSet, boolean isRoot,
                       List<TreeNode> ans) {
    if (root == null)
      return null;

    final boolean deleted = toDeleteSet.contains(root.val);
    if (isRoot && !deleted)
      ans.add(root);

    // If root is deleted, both children have the possibility to be a new root
    root.left = dfs(root.left, toDeleteSet, deleted, ans);
    root.right = dfs(root.right, toDeleteSet, deleted, ans);
    return deleted ? null : root;
  }
}
// code provided by PROGIEZ

1110. Delete Nodes And Return Forest LeetCode Solution in Python

class Solution:
  def delNodes(self, root: TreeNode, to_delete: list[int]) -> list[TreeNode]:
    ans = []
    toDeleteSet = set(to_delete)

    def dfs(root: TreeNode, isRoot: bool) -> TreeNode:
      if not root:
        return None

      deleted = root.val in toDeleteSet
      if isRoot and not deleted:
        ans.append(root)

      # If root is deleted, both children have the possibility to be a new root
      root.left = dfs(root.left, deleted)
      root.right = dfs(root.right, deleted)
      return None if deleted else root

    dfs(root, True)
    return ans
 # code by PROGIEZ