Delete Leaves With a Given Value
Medium · Trees · Tree · Depth-First Search · Binary Tree
Problem
Given the root of a binary tree and an integer target, delete every leaf whose value is target.
Deleting leaves can turn their parents into leaves. If such a parent also has value target, it must be deleted too, and this continues until no leaf with value target remains.
Return the root of the resulting tree, which may be empty (shown as []).
Examples
Input: root = [5,5,3,5,5,None,5], target = 5 Output: [5,None,3]
The whole left subtree of 5s disappears, and so does the leaf 5 under 3; the root survives because 3 still hangs from it.
Input: root = [2,2,2], target = 2 Output: []
Removing both leaves makes the root a target leaf too.
Input: root = [1,3,3,3,2], target = 3 Output: [1,3,None,None,2]
The leaf 3s go, but the 3 above the leaf 2 keeps a child and stays.
Constraints
- The number of nodes is in the range [1, 3000]
- 1 <= Node.val, target <= 1000
Approaches
- Baseline: remove the current target leaves, repeat — time O(n · h), space O(n)
Follow-up
The rule "delete a node once its subtree is gone and it matches" fits many tests besides equality. The use cases count how many nodes the cascade removes, and delete every leaf below a limit with the same bottom-up pass.
Related problems
Start free on Cariara · Coding problems · System design studio
