LeetCode 1325 - Delete Leaves With a Given Value

This problem asks us to repeatedly remove leaf nodes from a binary tree if their value matches a given target. A leaf no

leetcodemediumtreedepth-first-searchbinary-tree

LeetCode Problem 1325

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to repeatedly remove leaf nodes from a binary tree if their value matches a given target.

A leaf node is a node with no children, meaning both its left and right pointers are null (or None in Python). At first glance, the task may appear simple: traverse the tree and remove every leaf whose value equals target. However, there is an important complication.

Removing one leaf node can create new leaf nodes. If a parent node loses all its children because they were deleted, that parent may itself become a leaf. If that parent's value also equals target, it must be deleted too. This process continues recursively until no more qualifying leaf nodes remain.

The input consists of:

  • root, the root of a binary tree
  • target, an integer value

The expected output is the root of the modified binary tree after all possible deletions have been performed.

For example, suppose we remove a target-valued leaf. Its parent may suddenly become childless. If that parent also has the target value, it must now be removed as well. This cascading effect means we cannot simply delete nodes in a single top-down pass.

The constraints tell us several important things about the problem:

  • The tree contains between 1 and 3000 nodes.
  • Node values and target are between 1 and 1000.

A tree size of 3000 is moderate. This is small enough for recursive depth-first traversal to be feasible in most languages, although recursion depth should still be considered conceptually. Since we may need to revisit parent nodes after modifying children, a postorder traversal naturally fits the problem.

Several edge cases are important:

  • The root itself may eventually be deleted, meaning the answer becomes None or nil.
  • A chain of target-valued nodes may collapse upward repeatedly.
  • A node with the target value should not be removed unless it is a leaf.
  • A node may become removable only after its children are deleted.

These cases make naive top-down deletion error-prone.

Approaches

Brute Force Approach

A straightforward approach is to repeatedly scan the entire tree looking for removable leaves.

In each pass, we traverse the tree and delete any leaf node whose value equals target. After a full traversal, we check whether any deletion occurred. If deletions happened, we repeat the entire process because new removable leaves may have formed.

This approach is correct because eventually every newly created target-valued leaf will be discovered in a later traversal. Since the tree has a finite number of nodes, the process must terminate.

However, this method is inefficient. In the worst case, we may remove only one node per traversal. If the tree has n nodes, we could end up traversing the tree n times, leading to quadratic complexity.

For example, consider a skewed tree where every node equals target. We remove the bottom leaf first, then its parent becomes removable, then the next parent, and so on. This creates O(n) traversals, each costing O(n).

Optimal Approach, Postorder DFS

The key insight is that whether a node should be deleted depends entirely on the final state of its children.

If both children have already been processed and removed, the current node might become a leaf. Therefore, we should process children before processing the parent.

This naturally suggests a postorder depth-first traversal:

  1. Recursively process the left subtree.
  2. Recursively process the right subtree.
  3. Decide whether the current node should remain.

After recursively updating both children, we check:

  • Is the current node a leaf?
  • Does its value equal target?

If both conditions are true, we delete the node by returning None (nil in Go). Otherwise, we return the node itself.

This approach visits each node exactly once, making it efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(h) Repeatedly traverses tree until no deletions occur
Optimal O(n) O(h) Single postorder DFS traversal

Here:

  • n is the number of nodes.
  • h is the tree height.

Algorithm Walkthrough

Optimal Postorder DFS Algorithm

  1. Start a recursive DFS traversal from the root.

We need information about the updated state of child nodes before deciding whether the current node should remain. This is why recursion is ideal. 2. Recursively process the left child.

Call the recursive function on node.left. The result represents the updated left subtree after all valid deletions. 3. Recursively process the right child.

Do the same for node.right. Again, this ensures all child deletions are completed first. 4. Update the current node's child pointers.

Assign the recursive results back:

  • node.left = processed_left
  • node.right = processed_right

This ensures removed nodes become None. 5. Check whether the current node should be deleted.

A node is removable only if:

  • node.val == target
  • node.left is None
  • node.right is None

The second and third conditions guarantee the node is currently a leaf. 6. Delete removable nodes.

If the node qualifies for deletion, return None.

Returning None effectively removes the node from its parent. 7. Keep valid nodes.

If the node should remain, return the node itself. 8. Return the processed root.

After DFS completes, the returned root may be unchanged, partially modified, or entirely deleted.

Why it works

The correctness relies on a postorder invariant:

Before deciding whether a node should be deleted, both of its subtrees have already been fully processed.

Because children are finalized first, we know whether the current node has become a leaf after deletions. This guarantees that every removable node is detected exactly once, including nodes that only become removable after their children disappear.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def removeLeafNodes(
        self,
        root: Optional[TreeNode],
        target: int
    ) -> Optional[TreeNode]:

        def dfs(node: Optional[TreeNode]) -> Optional[TreeNode]:
            if not node:
                return None

            node.left = dfs(node.left)
            node.right = dfs(node.right)

            if (
                node.val == target
                and node.left is None
                and node.right is None
            ):
                return None

            return node

        return dfs(root)

The implementation follows the postorder DFS strategy exactly.

The nested dfs function processes one node at a time. The base case handles None nodes immediately by returning None.

The recursive calls process the left and right subtrees first. Their returned values are reassigned to node.left and node.right, ensuring any deleted child nodes are properly removed.

After both children have been processed, the node checks whether it has become a target-valued leaf. If so, returning None removes the node from the tree.

Finally, dfs(root) returns the updated tree root, which may itself be deleted.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func removeLeafNodes(root *TreeNode, target int) *TreeNode {
    var dfs func(node *TreeNode) *TreeNode

    dfs = func(node *TreeNode) *TreeNode {
        if node == nil {
            return nil
        }

        node.Left = dfs(node.Left)
        node.Right = dfs(node.Right)

        if node.Val == target &&
            node.Left == nil &&
            node.Right == nil {
            return nil
        }

        return node
    }

    return dfs(root)
}

The Go implementation closely mirrors the Python version.

The main language-specific difference is the use of nil instead of None. Since Go uses pointers for tree nodes, removing a node simply means returning nil.

Go also requires explicit declaration of the recursive function variable before assigning the anonymous function, which is why:

var dfs func(node *TreeNode) *TreeNode

appears before the function definition.

No integer overflow concerns exist here because node values are very small.

Worked Examples

Example 1

Input:

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

Initial tree:

        1
       / \
      2   3
     /   / \
    2   2   4

Traversal occurs bottom-up.

Node Processed Action Result
Left leaf 2 Remove None
Right subtree leaf 2 Remove None
Node 4 Keep Still leaf
Parent 2 Becomes leaf and equals target Remove
Node 3 Not target Keep
Root 1 Not target Keep

Final tree:

    1
     \
      3
       \
        4

Output:

[1,null,3,null,4]

Example 2

Input:

root = [1,3,3,3,2]
target = 3

Initial tree:

        1
       / \
      3   3
     / \
    3   2

Processing order:

Node Processed Action
Leaf 3 Remove
Leaf 2 Keep
Left 3 parent Not removable, still has child 2
Right 3 Remove
Root 1 Keep

Final tree:

      1
     /
    3
     \
      2

Output:

[1,3,null,null,2]

Example 3

Input:

root = [1,2,null,2,null,2]
target = 2

Initial tree:

      1
     /
    2
   /
  2
 /
2

Processing:

Step Removed Node
1 Bottom leaf 2
2 Parent becomes leaf 2
3 Next parent becomes leaf 2
4 Root 1 remains

Final tree:

1

Output:

[1]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node is visited exactly once
Space O(h) Recursive call stack proportional to tree height

The algorithm performs a single DFS traversal. Each node is processed once, and each operation inside the recursion takes constant time.

The space complexity comes entirely from recursion depth. In a balanced tree, height is approximately O(log n). In the worst-case skewed tree, height becomes O(n).

Test Cases

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

def tree_to_list(root):
    if not root:
        return []

    result = []
    queue = [root]

    while queue:
        node = queue.pop(0)

        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)

    while result and result[-1] is None:
        result.pop()

    return result

sol = Solution()

# Example 1
root = TreeNode(
    1,
    TreeNode(2, TreeNode(2)),
    TreeNode(3, TreeNode(2), TreeNode(4))
)
assert tree_to_list(
    sol.removeLeafNodes(root, 2)
) == [1, None, 3, None, 4]  # cascading deletions

# Example 2
root = TreeNode(
    1,
    TreeNode(3, TreeNode(3), TreeNode(2)),
    TreeNode(3)
)
assert tree_to_list(
    sol.removeLeafNodes(root, 3)
) == [1, 3, None, None, 2]  # partial subtree removal

# Example 3
root = TreeNode(
    1,
    TreeNode(2, TreeNode(2, TreeNode(2)))
)
assert tree_to_list(
    sol.removeLeafNodes(root, 2)
) == [1]  # chain deletion upward

# Single node removed
root = TreeNode(1)
assert sol.removeLeafNodes(root, 1) is None  # root deletion

# Single node preserved
root = TreeNode(1)
assert tree_to_list(
    sol.removeLeafNodes(root, 2)
) == [1]  # target mismatch

# Internal target node not leaf
root = TreeNode(2, TreeNode(3))
assert tree_to_list(
    sol.removeLeafNodes(root, 2)
) == [2, 3]  # target node retained

# Balanced tree with no removals
root = TreeNode(
    5,
    TreeNode(3),
    TreeNode(8)
)
assert tree_to_list(
    sol.removeLeafNodes(root, 2)
) == [5, 3, 8]  # no matching leaves

# Entire tree removed
root = TreeNode(
    2,
    TreeNode(2),
    TreeNode(2)
)
assert sol.removeLeafNodes(root, 2) is None  # full collapse
Test Why
Example 1 Validates cascading removals
Example 2 Ensures only removable target leaves disappear
Example 3 Tests repeated upward deletion
Single node removed Confirms root can become None
Single node preserved Verifies non-target root remains
Internal target node not leaf Ensures non-leaf targets are not removed
Balanced tree with no removals Confirms unchanged output
Entire tree removed Tests complete tree collapse

Edge Cases

The root node gets deleted

One subtle case occurs when the root itself becomes removable. For example:

root = [1]
target = 1

The root is already a leaf and matches the target, so the entire tree disappears. A buggy implementation may forget to return None as the final answer. This implementation handles it naturally because the recursive function returns None, and dfs(root) becomes the final result.

Cascading deletions upward

A chain of target-valued nodes can trigger repeated removals.

Example:

1
|
2
|
2
|
2

The bottom node is removed first. This causes its parent to become a leaf, which is then removed, continuing upward. A top-down traversal often misses this because it checks parents too early. Postorder traversal guarantees correctness because parents are evaluated only after children are finalized.

Target-valued internal nodes should remain

A node equal to target should not be removed if it still has children.

Example:

    2
   /
  3

The root value equals the target, but it is not a leaf. A careless implementation might remove it immediately. This solution explicitly checks both child pointers before deletion, ensuring only leaves are removed.

Trees with no matching target leaves

If no leaf matches the target, the tree should remain unchanged.

Example:

    5
   / \
  3   8

with target = 2.

The algorithm still traverses every node, but no deletions occur. Since every node returns itself unchanged, the original structure is preserved exactly.