Another Casual Coder

Here is a problem: you're given a binary tree, say something like this:


Now what we want to do is delete all the leaves from this tree whose value is equal to a certain target value. For this example's sake, the target value will be 5. That seems pretty straightforward: traverse down the tree, and the moment that you find a leave whose value equals to 5, chop it off:


But hang on, what if the problem requires you to ensure that the remaining tree, after deleting any leaf whose value was 5, does not have any resulting leaf with value equals to five? Suppose for example that instead of "4", that node had the value "5":


It would then trigger a cascading event where not only the "5" leaves would be deleted, but also their parent would be deleted too. This is because after deleting the "5"s, you'd end up with a new tree with new leaves whose values are also 5 :). Those should be deleted too. How to do that?


A simple approach would be a DFS (Depth-First Search) but using Post-Order (left, right, current) traversal. Basically ensure to process the left, process the right, and if the current node, for whatever reason, suddenly becomes (became?) a leaf whose value equals to the target, take care of it too. Short code is down below. Cheers, Marcelo.

static void DeleteLeaves(Tree parentNode,
Tree currentNode,
bool isLeft,
int target)
{
if (currentNode == null) return;

DeleteLeaves(currentNode, currentNode.left, true, target);
DeleteLeaves(currentNode, currentNode.right, false, target);

if (currentNode.left == null && currentNode.right == null && currentNode.value == target)
if (parentNode == null) currentNode = null;
else if (isLeft) parentNode.left = null;
else parentNode.right = null;
}