Leetcode discuss: 1110. Delete Nodes And Return Forest

Here is the link.

C# mock interview practice on June 26, 2020

June 26, 2020
Introduction

It is my mock interview practice and it took me more than 30 minutes to write bug-free code.

Problem statement:
Given a binary tree with distinct value in each node, given an integer array, delete those nodes in the tree, and return all trees with root node.

Things to work on:

1. Find those nodes to be deleted;
2. Set those nodes's left and right child to null;
3. Also, if the node has a parent node, then the parent node should also be updated with left or right child node and set to null if need.

The solution is to run preorder traversal once, and put all integer into a hashset, and then pass parent node in function applyPreorderTraversal design.

public class Solution {
    public IList<TreeNode> DelNodes(TreeNode root, int[] to_delete) {
        if(root == null)
            return new List<TreeNode>(); 
        
        var list = new List<TreeNode>(); 
        var set = new HashSet<int>(to_delete); 
        
        TreeNode parent = null;
            
        applyPreorderTraversal(root, list, parent, set); 
        return list; 
    }
    
    private void applyPreorderTraversal(TreeNode root,IList<TreeNode> list, TreeNode parent, HashSet<int> set )
    {
        if(root == null)
            return; 
        
        var current = root.val;
        if(parent == null || set.Contains(parent.val))
        {
            if(!set.Contains(current))
            {
                list.Add(root);       
            }
        }
        
        applyPreorderTraversal( root.left, list, root , set );
  applyPreorderTraversal( root.right, list, root, set );
        
        // set null pointer 
        if(set.Contains(current))
        {
            root.left  = null;
            root.right = null;
        }
        
        if(root.left != null && set.Contains(root.left.val))
        {
            root.left = null;
        }
        
         if(root.right != null && set.Contains(root.right.val))
        {
            root.right = null;
        }
    }    
}