Delete Leaves With a Given Value

MEDIUM✓ CHIP-TIMEDLC #1325 — FULL STATEMENT ↗

The drill: Strip every leaf carrying a target value — and keep stripping, since removing a leaf can turn its parent into a new leaf that also needs checking against the same target.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A binary tree and a target value arrive, and any leaf whose value matches the target gets removed.

Removing a leaf can turn its parent into a brand-new leaf, and if that parent also matches the target, it gets removed too — the stripping cascades upward along a branch for as long as matches keep appearing.

The result is the tree after every possible cascade has finished, handed back as its root, which can end up null if the cascade eats the whole tree.

EX 01

root = [] · target = 5

→ []

EMPTY TREE

EX 02

root = [1] · target = 1

→ []

SINGLE NODE, WHOLE TREE REMOVED

EX 03

root = [1] · target = 2

→ [1]

SINGLE NODE, TARGET ABSENT

tree sizes stay in the low thousands of nodes
values are ordinary integers, target included
a whole branch can vanish if every node on it matches the target
the cascade only stops once no remaining leaf matches

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

One sweep that deletes today's leaves isn't the whole answer — a parent can become a leaf only after its own child is gone, and it might match the target too.

HINT 2 THE STRUCTURE

Deletions cascade upward, one generation at a time, only along branches where every descendant also happened to match.

HINT 3 ONE STEP FROM THE ANSWER

Postorder: clean both children first, THEN check if the current node is now childless and equal to target. Doing the check after the recursive calls (not before) makes the cascade happen for free in a single pass.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE CASCADE UPPATTERN · POSTORDER PRUNEroot = [1, 2, null, 1, null, 1, null] · target = 1

STEP 1

Postorder: clean both children first, THEN check if this node is now a childless leaf equal to target 1.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/delete-leaves-with-a-given-value.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
        if not root:
            return None
        root.left = self.removeLeafNodes(root.left, target)
        root.right = self.removeLeafNodes(root.right, target)
        if not root.left and not root.right and root.val == target:
            return None
        return root

TIME O(N)SPACE O(H)PYTHON · RACE PACE · 9 LN

class Solution:
    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
        def prune_one_level(node: Optional[TreeNode], state: dict) -> Optional[TreeNode]:
            if node is None:
                return None
            if node.left is None and node.right is None:
                if node.val == target:
                    state["changed"] = True
                    return None
                return node
            # a non-leaf here is NOT re-checked even if its children vanish
            # this pass — that only happens on the NEXT full sweep
            node.left = prune_one_level(node.left, state)
            node.right = prune_one_level(node.right, state)
            return node

        while True:
            state = {"changed": False}
            root = prune_one_level(root, state)
            if not state["changed"]:
                break
        return root

TIME O(N·H)SPACE O(H)PYTHON · TRAINING PACE · 22 LN

class Solution {
    public TreeNode removeLeafNodes(TreeNode root, int target) {
        if (root == null) {
            return null;
        }
        root.left = removeLeafNodes(root.left, target);
        root.right = removeLeafNodes(root.right, target);
        if (root.left == null && root.right == null && root.val == target) {
            return null;
        }
        return root;
    }
}

TIME O(N)SPACE O(H)JAVA · RACE PACE · 13 LN

class Solution {
    private int target;

    public TreeNode removeLeafNodes(TreeNode root, int target) {
        this.target = target;
        boolean[] changed = new boolean[1];
        while (true) {
            changed[0] = false;
            root = pruneOneLevel(root, changed);
            if (!changed[0]) {
                break;
            }
        }
        return root;
    }

    private TreeNode pruneOneLevel(TreeNode node, boolean[] changed) {
        if (node == null) {
            return null;
        }
        if (node.left == null && node.right == null) {
            if (node.val == target) {
                changed[0] = true;
                return null;
            }
            return node;
        }
        // a non-leaf here is NOT re-checked even if its children vanish this
        // pass — that only happens on the NEXT full sweep
        node.left = pruneOneLevel(node.left, changed);
        node.right = pruneOneLevel(node.right, changed);
        return node;
    }
}

TIME O(N·H)SPACE O(H)JAVA · TRAINING PACE · 34 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED