Delete Leaves With a Given Value - Leetcode 1325 - Python

0:00 - Read the problem
1:12 - Drawing Explanation 1
5:23 - Coding Solution 1
6:46 - Drawing Explanation 2
11:05 - Coding Solution 2

leetcode 1325

#neetcode #leetcode #python

[kareni]

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

[PegasusKr]

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

thanks for the explanation

[MP-nyep]

Thank you so much for the daily problems.

[DeathSugar]

Dunno why is it medium. Pretty straightforward solution.

[nirmalgurjar]

Accepted Java Iterative Solution using map and stack:

class Solution {
public TreeNode removeLeafNodes(TreeNode root, int target) {

Map<TreeNode, TreeNode> parentMap = new HashMap();
Stack<TreeNode> 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 && {

added = true;
stk.push(node); // add back current node to stack
stk.push(node.right);
parentMap.put(node.right, node);
}

if (node.left != null && {

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;
}
}

[jayberry]

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