Delete Nodes and Return Forest Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon Bloomberg ByteDance Facebook Google Intuit Microsoft Oracle Salesforce
Binary Tree Depth First Search TreeViews 1729

Problem Statement

The Delete Nodes and Return Forest LeetCode Solution – “Delete Nodes and Return Forest” states that given the root of the binary tree where each node has a distinct value. We’re also given an array,  to_delete, where we need to delete all the nodes with values contained in the above array. After deleting, we need to return the roots of all the trees in any order.

Example:

Input:  root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

Explanation:

  • Delete nodes with value 3 and value 5.
  • We’re left with trees rooted at values 1,6 and 5.
Input:  root = [1,2,4,null,3], to_delete = [3]
Output: [[1,2,4]]

Explanation:

  • After deleting 3 (leaf node), we still have the same rooted binary tree.

Approach

Idea:

  1. The main idea to solve this problem is to use Recursion.
  2. Perform Depth-First Search of the above binary tree and when we’re done with the child nodes of the current root node, check if the current value of the node should be deleted or not?
    1. If the current node will be deleted, there will be at most 2 new rooted trees we can have.
    2. Insert all those possible new rooted trees into our answer, and return the null pointer.
    3. If the current node won’t be deleted, then return the root as it is.
  3. Also, when the recursion ends, it will return whether the root node will be deleted or not?
  4. So, if the root node is not deleted insert the root node into our answer.

Code

Delete Nodes and Return Forest Leetcode C++ Solution:

class Solution {
public:
    TreeNode* recurse(TreeNode* root,vector<int>& to_delete,vector<TreeNode*>& ans){
        if(root==nullptr){
            return root;
        }
        root->left = recurse(root->left,to_delete,ans);
        root->right = recurse(root->right,to_delete,ans);
        if(binary_search(to_delete.begin(),to_delete.end(),root->val)){
            if(root->left!=nullptr){
                ans.push_back(root->left);
            }
            if(root->right!=nullptr){
                ans.push_back(root->right);
            }
            return nullptr;
        }
        return root;
    }
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        vector<TreeNode*> ans;
        sort(to_delete.begin(),to_delete.end());
        if(recurse(root,to_delete,ans)!=nullptr){
            ans.push_back(root);
        }
        return ans;
    }
};

Delete Nodes and Return Forest Leetcode Java Solution:

class Solution {
    List<TreeNode> ans;
    Set<Integer> delete_set;
    TreeNode recurse(TreeNode root){
        if(root==null){
            return null;
        }
        root.left = recurse(root.left);
        root.right = recurse(root.right);
        if(delete_set.contains(root.val)){
            if(root.left!=null){
                ans.add(root.left);
            }
            if(root.right!=null){
                ans.add(root.right);
            }
            return null;
        }
        return root;
    }
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        delete_set = new HashSet<>();
        ans = new ArrayList<>();
        for(int i:to_delete){
            delete_set.add(i);
        }
        if(recurse(root)!=null){
            ans.add(root);
        }
        return ans;
    }
}

Complexity Analysis for Delete Nodes and Return Forest Leetcode Solution

Time Complexity

The time complexity of the above code is O(NlogM+MlogM) since we traverse the entire input tree once where N = a total number of nodes in the tree, M = size of to_delete input array.

Note that we’re traversing the entire input tree exactly once for every node, we are searching the value in the to_delete set which takes a logarithmic time.

Space Complexity

The space complexity of the above code is O(1) if we store do the binary search directly after sorting or O(N) if we store entries to_delete array in a set.

Translate »