Delete Leaves With a Given Value

Difficulty: Medium Source: NeetCode

Problem

Given a binary tree root and an integer target, delete all the leaf nodes with value target. Note that once you delete a leaf node with value target, if its parent node becomes a leaf node and has the value of target, it should also be deleted (you need to continue doing this until you can’t).

Example 1: Input: root = [1,2,3,2,null,2,4], target = 2 Output: [1,null,3,null,4]

Example 2: Input: root = [1,3,3,3,2], target = 3 Output: [1,3,null,null,2]

Constraints:

The number of nodes in the tree is in the range [1, 200]

1 <= Node.val, target <= 1000

Prerequisites

Before attempting this problem, you should be comfortable with:

Post-order DFS — Process children before parents (bottom-up) so we can clean up leaf chains naturally
Recursive Tree Modification — Returning updated node references from DFS to rewire the tree
Leaf Node Definition — A node with no left and no right child

The cascading deletion (a parent becoming a leaf after its child is deleted) is naturally handled by post-order traversal. We process children first, then check the current node. By the time we examine a node, its children have already been cleaned up. If after cleaning up children, the current node has no children AND has the target value, it too becomes a deletion candidate — we return null to the parent.

Algorithm

DFS in post-order: recurse left, recurse right, then process current node
Assign node.left = dfs(node.left) and node.right = dfs(node.right)
If the current node is now a leaf (no left, no right) and node.val == target, return null (delete it)
Otherwise return the node

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def remove_leaf_nodes(root, target):
    def dfs(node):
        if not node:
            return None

        # Post-order: process children first
        node.left = dfs(node.left)
        node.right = dfs(node.right)

        # Now check if this node has become a deletable leaf
        if not node.left and not node.right and node.val == target:
            return None  # Delete this node

        return node  # Keep this node

    return dfs(root)

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def level_order(root):
    if not root:
        return []
    result, queue = [], [root]
    while queue:
        node = queue.pop(0)
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

# --- tests ---
# [1,2,3,2,null,2,4], target=2
#       1
#      / \
#     2   3
#    /   / \
#   2   2   4
root1 = build_tree([1, 2, 3, 2, None, 2, 4])
print("Before:", level_order(root1))  # [1, 2, 3, 2, 2, 4]
root1 = remove_leaf_nodes(root1, 2)
print("After:", level_order(root1))   # [1, 3, 4]

# [1,3,3,3,2], target=3
root2 = build_tree([1, 3, 3, 3, 2])
print("Before:", level_order(root2))  # [1, 3, 3, 3, 2]
root2 = remove_leaf_nodes(root2, 3)
print("After:", level_order(root2))   # [1, 3, 2]

# Edge: entire tree is the target leaf
root3 = build_tree([1])
root3 = remove_leaf_nodes(root3, 1)
print("After deleting root:", root3)  # None

# Chain deletion
root4 = build_tree([1, 2, None, 2, None, 2])
print("Before chain:", level_order(root4))  # [1, 2, 2, 2]
root4 = remove_leaf_nodes(root4, 2)
print("After chain:", level_order(root4) if root4 else [])  # [1]

Complexity

Time: O(n) — every node is visited exactly once
Space: O(h) — recursion stack depth equals tree height

Common Pitfalls

Using preorder (top-down) instead of postorder. If you check the current node before processing its children, you might miss cascading deletions. A node that’s not a leaf yet could become one after its target-valued leaf child is removed. Post-order handles this naturally.

Forgetting to reassign node.left and node.right. The deletion works by returning None from the recursive call and assigning it back to node.left or node.right. If you don’t do the assignment, the tree isn’t actually modified.

Not checking both leaf conditions. A node is only deletable if it’s a leaf (no left AND no right child) AND its value equals target. A node with one remaining child is not a leaf even if its value is the target.

Note Book