[Java] Recursive Soultion using IBH method
Hypothesis:\nFirst Step: Let\'s design the hypothesis for the problem:\nWe will create a function which will take root node of the tree, a set of integers repre
Hypothesis:\nFirst Step: Let\'s design the hypothesis for the problem:\nWe will create a function which will take root node of the tree, a set of integers representing the nodes to be deleted and it will put the forest output in a list.\n\nSecond Step(making our input smaller): We will call the same hypothesis by making our input smaller. And it will give us the forest output for the smaller input.\n\nBase Codition:\nThis one is simple. If you are given a null or empty node there is nothing to process, so we just return.\n\nInduction(Most important part of this recursion):\nWe got the intended output from these two lines, now what to do with the current node(root node)? \n```\n        delNodes(root.left, root, set, res);\n        delNodes(root.right, root, set, res);\n```\nIf it is the node that we need to delete we need to take care of it\'s parent and it\'s childs. Clearly if it is deleted, all of it\'s chlidren will become the root of their respective tree. And, we know a root can not have any parent.\n```\n            if(root.left!=null){\n                res.add(root.left);\n            }\n            if(root.right!=null){\n                res.add(root.right);\n            }\n            root.left = null;\n            root.right = null;\n```\nNow, we also need to tell parent of root that it\'s children is gone. So, we modify our hypothesis so that it take parent as parameter as well and we reset parent\'s child, if it is needed.\n\nOne last thing. Since, the initial root of the given tree also needs checked, so we do that in our given function.\n\n```\nprivate void delNodes(TreeNode root, TreeNode parent, Set<Integer> set,List<TreeNode> res) {\n        if(root==null){\n            return;\n        }    \n        \n        delNodes(root.left, root, set, res);\n        delNodes(root.right, root, set, res);\n        \n        if(set.contains(root.val)){\n            if(root.left!=null){\n                res.add(root.left);\n            }\n            if(root.right!=null){\n                res.add(root.right);\n            }\n            root.left = null;\n            root.right = null;\n            if(parent!=null){\n                if(parent.left==root){\n                   parent.left = null; \n                }else{\n                    parent.right = null; \n                }\n            }\n        }            \n    }\n    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {\n        List<TreeNode> res = new ArrayList<TreeNode>(); \n        if(root==null){\n            return res;\n        }         \n        Set<Integer> set = new HashSet<>();\n        for(int a: to_delete){\n            set.add(a);\n        }        \n        if(!set.contains(root.val)){\n            res.add(root);\n        }\n        delNodes(root, null, set,res);\n        return res;\n    }\n```\n\nHope this clarifies any doubt anyone might have for this problem.\n\nAll kinds of tree, linkedlist problem can be solved using IBH (Induction, Base Condition, Hypothesis) strategy. (Credit: https://www.youtube.com/watch?v=Xu5RqPdABRE (hindi))\n**(Disclaimer: This is not a promotion for this video. I am non-indian but i do understand hindi. I do not have any affiliation with this channel. His videos on Recursion and DP are helping me a lot.)**
[]