Delete Leaves With a Given Value

medium tree dfs

Problem

Given a binary tree root and an integer target, delete all leaf nodes with value equal to target. After deleting a leaf, its parent may become a leaf; if so, delete it as well, repeating until no more deletions are possible.

Inputroot = [1,2,3,2,null,2,4], target = 2

Output[1,null,3,null,4]

Leaves with value 2 are deleted; their parent (2) then becomes a leaf and is also pruned.

tree (level-order, null=#)

target

def remove_leaf_nodes(root, target):
    if not root: return None
    root.left = remove_leaf_nodes(root.left, target)
    root.right = remove_leaf_nodes(root.right, target)
    if not root.left and not root.right and root.val == target:
        return None
    return root

function removeLeafNodes(root, target) {
  if (!root) return null;
  root.left = removeLeafNodes(root.left, target);
  root.right = removeLeafNodes(root.right, target);
  if (!root.left && !root.right && root.val === target) return null;
  return root;
}

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

TreeNode* removeLeafNodes(TreeNode* root, int target) {
    if (!root) return nullptr;
    root->left = removeLeafNodes(root->left, target);
    root->right = removeLeafNodes(root->right, target);
    if (!root->left && !root->right && root->val == target) return nullptr;
    return root;
}

Explanation

We want to delete leaves whose value equals target, but with a twist: once a leaf disappears, its parent might become a new leaf and need deleting too. Doing this naively could mean many passes over the tree.

A single post-order DFS handles the whole chain reaction at once. The trick is to fix up the children before looking at the current node, so by the time we judge a node, its branches already reflect any deletions below.

Each call does root.left = removeLeafNodes(root.left, target) and the same for the right side. These reassignments are what actually prune branches — a deleted child returns None, so the parent's pointer becomes empty.

After the children are settled, we check: if both sides are now empty and root.val == target, this node is a matching leaf, so we return None to delete it. Otherwise we keep it by returning root.

Example: [1,2,3,2,null,2,4] with target = 2. The leaf 2s vanish first; that turns their parent 2 into a leaf, which then also matches and is pruned in the same upward pass, leaving [1,null,3,null,4].

Time: O(n) Space: O(h)