Deleting leaves of a certain kind

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

Comments

  1. Very slick, Marcelo! It's a classical problem for post-order traversal.

    ReplyDelete
  2. Indeed. Funny story is when I first saw this problem for whatever reason my brain got stuck into pre-order and couldn’t get out of that state. Later on the post order came. Sometimes we just need a thinking break to clear things up!

    ReplyDelete
    Replies
    1. Definitely! After solving a few problems using DP, I always need a long-ish break to stop trying to solve even trivial problems using it :) Good thing there is always plenty of work to take our minds off :) Keep these awesome problems coming, Marcelo!

      Delete

Post a Comment

Popular posts from this blog

Advent of Code - Day 6, 2024: BFS and FSM

Golang vs. C#: performance characteristics (simple case study)

Advent of Code - Day 7, 2024: Backtracking and Eval