Delete Nodes And Return Forest - Leetcode 1110 - Python

[@shyamsundarmg1497]

5:18 "There's no magic way; it's not just going to magically pop up into your mind, so DON'T BE LAZY; get a piece of paper, draw out some examples, and see what you can come up with." GOLDEN WORDS... I was too lazy and came to look up at the video to see solution without trying much, Thank You NeetCode, this really was a motivation that stirred my ego and I ended up doing the first problem with 100.00% better in time... Lots of love and respect to you Navdeep!!

[@aadil4236]

Solved it by myself in O(n) space and O(n) time. Thank you for teaching me Navdeep! I am better than my past self because of NeetCode. Thank you!!

[@AKProductionsTelugu]

This problem is even easier by following post order traversal get left node get right node check if root needs to be removed if yes, null check and add two children to roots list and return null else return node This way we don't need to maintain two sets TreeNode dfs(TreeNode root) { if(root == null) return null; TreeNode left = dfs(root.left); TreeNode right = dfs(root.right); if(nodesToDelete.contains(root.val)) { if(left != null) trees.add(left); if(right != null) trees.add(right); return null; } root.left = left; root.right = right; return root; }

[@qulinxao]

class Solution: def delNodes(self, r: Optional[TreeNode], t: List[int]) -> List[TreeNode]: t,o=set(t),[] def f(p): if p: p.left,p.right=f(p.left),f(p.right) if p.val not in t:return p o.extend((p.left,p.right)) o.append(f(r)) return [p for p in o if p]

[@pratyushthakur8478]

I haven't practiced trees in a while but happy that the daily is making me revise old topics.

[@freecourseplatformenglish2829]

Same for me.

[@freecourseplatformenglish2829]

Sovled it on my own. I found these daily questions best to practise DSA questions and revise my concept.

[@DNKF]

First! Love super early videos these days. Will start reading the neetcode new chapter tonight.

[@NeetCodeIO]

As long as it's not a hard problem I can usually pump these out fast. As difficult it is to solve a LC hard, it's even more time consuming to explain them tbh

[@DNKF]

@@NeetCodeIO for hard one, sometime I could not figure them out until watching your videos 😅

[@chrischika7026]

@@NeetCodeIO what type of traversal is your solution preorder or postorder ?

[@maanas_sehgal]

I got a 70 line solution in java, did use like 2 sets, but got last pos on leetcode even on O(n)😢

[@AKProductionsTelugu]

Unlike others but in Java i almost everytime get 0ms its sp satisfying... and you might cross check your code for unnecessary checks and iterations

[@alijohnnaqvi6383]

Approach Beats 99% of users with Python :) Recursively go through each node in a tree If you have to delete this node from tree, add its left and right children to output as they are forest roots now If you do not have to delete the node, return it as it, because at the end we care for highest level node Complexity Time complexity: O(n) Space complexity: O(n) 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: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]: output = [] to_delete = set(to_delete) def dfs(root,parent): if not root: return None left = dfs(root.left,root) right = dfs(root.right,root) if root.val in to_delete: if left is not None: output.append(left) if right is not None: output.append(right) if parent is not None: if parent.left==root: parent.left=None else: parent.right= None else: return root r = dfs(root,None) if r is not None: output.append(r) return output

[@yang5843]

I was hoping you would make a video, thanks

[@playjar4854]

class Solution: def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]: res=[] to_delete=set(to_delete) def dfs(root): if not root: return False result=dfs(root.left) if result: if root.left.left: res.append(root.left.left) if root.left.right: res.append(root.left.right) root.left=None result=dfs(root.right) if result: if root.right.left: res.append(root.right.left) if root.right.right: res.append(root.right.right) root.right=None if root.val in to_delete: return True return False result=dfs(root) if result: if root.left: res.append(root.left) if root.right: res.append(root.right) else: res.append(root) return res

[@aashishbathe]

This is what I coded up. Simultaneous addition if its not to be deleted. Also didn't add everything and delete it. class Solution: def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]: to_delete = set(to_delete) roots = [] if root.val not in to_delete: roots.append(root) def dfs(node, par): nonlocal roots if node.val in to_delete: if node.left and node.left.val not in to_delete: roots.append(node.left) if node.right and node.right.val not in to_delete: roots.append(node.right) if par: if par.left and par.left.val == node.val: par.left = None else: par.right = None if node.left: dfs(node.left, node) if node.right: dfs(node.right, node) dfs(root, None) return roots

[@MP-ny3ep]

Great explanation as always. Thank you

[@chien-yuyeh9386]

Nice question 🎉

[@tuandino6990]

Stack, tree and forest 🎉🎉🎉

[@Yoo_broo_Jr]

Bruhh just love your consistency in posting every solutions for the problem of the day. Keep going bruhh LOVE YOU😇🤗

[@galkk3]

my solution, same idea but less concise: delete = set(to_delete) res = [] if root.val not in delete: res.append(root) def dfs(node, parentDeleted): if not node: return False if node.val in delete: dfs(node.left, True) dfs(node.right, True) return True if parentDeleted: res.append(node) if dfs(node.left, False): node.left = None if dfs(node.right, False): node.right = None return False dfs(root, False) return res

[@jokerlex6976]

sorry for the oot, but what tools did you use when drawing the algorithm ?

[@スヘア]

Looks like one note to me

[@DeathSugar]

Gosh I hate recursive calls. Solved with while loop using some extra space to check if node has parents (meaning is not disjointed)

[@InquisitiveLittleSteps]

Thank you

[@abdulrehmanmughal2197]

Hi, man great explanation as always ❤. I'm new to leetcode I have been solving some easy problems on my own but I can not even sometimes solve an easy problem. Sometimes I can even come up with the logic but I can not code it out. (I am using java.) Can you please guide me how can I get better at coding and finding solutions of tough problems.

[@anantakarmakar3458]

class Solution { public: vector res; unordered_set del; void dfs(TreeNode *&root) { if (root == NULL) return; dfs(root->left); dfs(root->right); if (del.find(root->val) != del.end()) { if (root->left) res.push_back(root->left); if (root->right) res.push_back(root->right); root = NULL; delete root; } } vector delNodes(TreeNode *root, vector &to_delete) { for (int i = 0; i < to_delete.size(); i++) { del.insert(to_delete[i]); } dfs(root); if (root) res.push_back(root); return res; } };

[@samjohn5042]

Would the space complexity not be O(n+m) because of the two hashsets?

[@pastori2672]

its so sad the only problem i missed is "maximum score from removing substring" because i misinterpreted it 😭

[@yuhangzhao3303]

I am thinking if this solution misses some cases. If we have a tree like [1,2,3,4,5], to_delete is [4,5], is this solution going to work? In this case, 4 is deleted first, the child of 4(5) doesn’t have a chance to be checked? Because 4 is changed to point to None.

[@aashishbathe]

This wasn't super tough, but then had some edge cases..

[@tusharbhatia5437]

Bro doesn't miss

[@sidazhong2019]

My code for this question is very long and ugly. As a tree problem, the code should not be so long. I just came here to confirm that this question is really that disgusting, and it seems that I was right.

[@giovannigeorgio3032]

hey can you post the iterative solution somewhere i can do the recursive bet cant do iterative

[@saikumaradapa3266]

A simple BFS solution in your style, is it? class Solution: def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]: target = set(to_delete) if not target: return [root] res = [] if root.val not in target: res.append(root) curr = TreeNode(-1, root) q = deque([curr]) while q: node = q.popleft() if node.left: q.append(node.left) if node.left and node.left.val in target: node.left = None if node.right: q.append(node.right) if node.right and node.right.val in target: node.right = None if node.val in target: if node.left and node.left.val not in target: res.append(node.left) if node.right and node.right.val not in target: res.append(node.right) return res

[@pastori2672]

cute problem 🥰

[@giovannigeorgio3032]

A simple recursive java solution class Solution { private List trees = new ArrayList(); private TreeNode helper(TreeNode root, Set to_delete){ if(root == null){ return null; } TreeNode leftTree = helper(root.left, to_delete); TreeNode rightTree = helper(root.right, to_delete); if(to_delete.contains(root.val)){ if(leftTree != null) trees.add(leftTree); if(rightTree != null) trees.add(rightTree); return null; } root.left = leftTree; root.right = rightTree; return root; } public List delNodes(TreeNode root, int[] to_delete) { Set del = new HashSet(); for( var i : to_delete ){ del.add(i); } TreeNode node = helper(root, del); if(node != null){ trees.add(node); } return trees; } }

[@stoney78us]

I might be wrong but it looks like the deleted nodes are still connected to theirs children even though the result still satisfied.

[@TWEEDOriginal]

// My JS solution using top-down deletion and collection var delNodes = function (root, to_delete) { to_delete = new Set(to_delete) const res = [] function dfs(node, parent) { if (!node) return let newParent = null // if node is deleted then it's children has no parent if (to_delete.has(node.val)) { if (parent) { if (parent?.left?.val === node.val) parent.left = null else parent.right = null } } else { if (!parent) res.push(node) newParent = node } dfs(node.left, newParent) dfs(node.right, newParent) } dfs(root, null) return res };

[@knight-uy7bp]

@neetcode Why is the java equivalent of the above code not working? class Solution { HashSet delSet = new HashSet(); HashSet resSet = new HashSet(); List res = new ArrayList(); // DFS , Hashset public List delNodes(TreeNode root, int[] to_delete) { for(int n: to_delete){ delSet.add(n); } dfs(root); for(TreeNode node: resSet){ res.add(node); } return res; } public TreeNode dfs(TreeNode node){ if(node == null){return null;} TreeNode res = node; if(delSet.contains(node.val)){ res = null; resSet.remove(node); if(node.left != null){ resSet.add(node.left); } if(node.right != null){ resSet.add(node.right); } } node.left = dfs(node.left); node.right = dfs(node.right); return res; } }

[@chrischika7026]

what type of traversal is this @NeetCodeIO

[@nirmalgurjar8181]

Post Order.

[@nirmalgurjar8181]

Post Order.