Delete Leaves With a Given Value - Leetcode 1325 - Python

[@krateskim4169]

Ayo the thumbnail😂

[@kareni7572]

Yes, The leaf node check should be done post order (not pre order) -- so that it will reach till parent

[@Pegasus02Kr]

honestly I doubt we will ever have chance to implement tree traversal with iterative approach...
thanks for the explanation

[@MP-ny3ep]

Thank you so much for the daily problems.

[@Ari-pq4db]

Thank You 🍃

[@user-rv1bx8hx4v]

Thank you!

[@DeathSugar]

Dunno why is it medium. Pretty straightforward solution.

[@chrischika7026]

look at the iterative.

[@DeathSugar]

@@chrischika7026 uglier and complicated, more memory footprint and not really outperforms recursive one. Would work on the languages which has no recursion, but they aren't on the language list in leetcode anyway, so why bother?

[@jayberry6557]

Is there any reason why would we use bfs in this case?

[@staywithmeforever]

We can use dfs also no problem.

[@staywithmeforever]

But if you wanna use bfs u need parent pointers that will be complicated.

[@staywithmeforever]

U have to make a while look and keep on deleting the parents while target!=root.val. so this makes O(n2)

[@nirmalgurjar8181]

Accepted Java Iterative Solution using map and stack:
class Solution {
public TreeNode removeLeafNodes(TreeNode root, int target) {
Map parentMap = new HashMap();
Stack stk = new Stack();
stk.push(root);
while (!stk.isEmpty()) {
TreeNode node = stk.pop();
if (node.right == null && node.left == null && node.val == target) { // delete this node
TreeNode parent = parentMap.get(node);
if (parent != null && parent.right == node) { // update parent right pointer to null
parentMap.remove(node);
parent.right = null;
}
if (parent != null && parent.left == node) { // update parent left pointer to null
parentMap.remove(node);
parent.left = null;
}
} else {
boolean added = false;
if (node.right != null && !parentMap.containsKey(node.right)) {
added = true;
stk.push(node); // add back current node to stack
stk.push(node.right);
parentMap.put(node.right, node);
}
if (node.left != null && !parentMap.containsKey(node.left)) {
if (!added) {
stk.push(node); // if not added ealier then add back
}
stk.push(node.left);
parentMap.put(node.left, node);
}
}
}
//if root only is pending and having value == target
if (root.left == null && root.right == null && root.val == target) {
return null;
}
return root;
}
}

[@advaitbajaj4241]

Sixty Nine!

[@ChiragMalaviya-so7tw]

Fourth

[@nqv497]

THIRD

[@ap2s2000]

420 everyday

[@AnordinaryMan007]

fifth

[@pastori2672]

[@dhruvgirigoswami5886]

FIRST!

[@dhruvgirigoswami5886]

SECOND!!

[@ap2s2000]

420 everyday