Delete Leaves With a Given Value
Description
You are given the root of a binary tree and an integer called target. Your task is to remove all leaf nodes from the tree whose value equals the target.
However, there is an important twist: after removing a leaf node, its parent might itself become a new leaf node. If that newly formed leaf also has a value equal to the target, it must be removed as well. This cascading deletion continues until no more leaf nodes with the target value remain in the tree.
A leaf node is any node that has no left child and no right child.
Examples
Example 1
Input: root = [1, 2, 3, 2, null, 2, 4], target = 2
Output: [1, null, 3, null, 4]
Explanation: The tree initially has three leaf nodes: the leftmost node with value 2, the left child of node 3 with value 2, and node 4. We remove the two leaf nodes that have value 2. After removing them, node 2 (the left child of the root) becomes a new leaf node, and since its value is also 2, we remove it as well. The final tree has root 1 with only the right subtree: node 3 with right child 4.
Example 2
Input: root = [1, 3, 3, 3, 2], target = 3
Output: [1, 3, null, null, 2]
Explanation: The leaf nodes are: node 3 (left-left child), node 2 (left-right child), and node 3 (right child of root). We remove leaf nodes with value 3: the left-left child and the right child of the root. After removal, the left child (node 3) still has child node 2, so it is not a leaf and remains. The right child of root is now null.
Example 3
Input: root = [1, 2, null, 2, null, 2], target = 2
Output: [1]
Explanation: The tree is a chain: 1 → 2 → 2 → 2. The bottom node 2 is a leaf and gets removed. Then its parent (also value 2) becomes a leaf and gets removed. Then the next parent (also value 2) becomes a leaf and gets removed. Only the root node 1 remains since its value is not equal to the target.
Constraints
- The number of nodes in the tree is in the range [1, 3000]
- 1 ≤ Node.val ≤ 1000
- 1 ≤ target ≤ 1000
Editorial
Brute Force
Intuition
The simplest way to think about this problem is to repeatedly scan the entire tree, find all current leaf nodes that have the target value, and remove them. After each full scan, new leaf nodes might form, so we scan again. We keep repeating this process until a full pass finds no target-valued leaves to remove.
Imagine you have a tree with sticky notes on some leaves. You walk around the tree, pluck off every leaf sticky-note that says the target number. But after you finish your walk, some branches that used to have children are now bare — they have become new leaves. So you walk around the tree again and pluck the new target-valued leaves. You keep walking and plucking until a full walk produces no removals.
Step-by-Step Explanation
Let's trace through Example 1: root = [1, 2, 3, 2, null, 2, 4], target = 2.
The tree structure is:
1
/ \
2 3
/ / \
2 2 4
Pass 1: Scan all nodes, identify and remove target-valued leaves.
Step 1: Check node 2 (left-left child). It has no children — it is a leaf. Its value is 2 = target. Remove it.
Step 2: Check node 2 (left child of node 3). It has no children — it is a leaf. Its value is 2 = target. Remove it.
Step 3: Check node 4 (right child of node 3). It has no children — it is a leaf. Its value is 4 ≠ target. Keep it.
Step 4: Check node 2 (left child of root). It still had child node 2, but that was removed. Now it has no children — skip for this pass since we already collected our removal list. We removed 2 nodes this pass.
Tree after pass 1:
1
/ \
2 3
\
4
Pass 2: Scan again since we made removals.
Step 5: Check node 2 (left child of root). It has no children — it is a leaf. Its value is 2 = target. Remove it.
Step 6: Check node 4. It is a leaf, value 4 ≠ 2. Keep it.
We removed 1 node this pass.
Tree after pass 2:
1
\
3
\
4
Pass 3: Scan again.
Step 7: No leaf node has value 2. Zero removals. Stop.
Final result: [1, null, 3, null, 4].
Brute Force — Multi-Pass Leaf Deletion — Watch how we repeatedly scan the tree, removing target-valued leaves each pass, until no more target leaves exist.
Algorithm
- Set a flag
changedto true - While
changedis true:
a. Setchangedto false
b. Traverse the entire tree
c. For each node, check if it is a leaf (no left or right child)
d. If it is a leaf and its value equals target, remove it by setting the parent's corresponding child pointer to null
e. Setchangedto true if any removal happened - Return the root (or null if root itself was removed)
Code
class Solution {
public:
bool removeLeaves(TreeNode* node, TreeNode* parent, bool isLeft, int target) {
if (!node) return false;
bool changed = false;
changed |= removeLeaves(node->left, node, true, target);
changed |= removeLeaves(node->right, node, false, target);
if (!node->left && !node->right && node->val == target) {
if (parent) {
if (isLeft) parent->left = nullptr;
else parent->right = nullptr;
}
return true;
}
return changed;
}
TreeNode* removeLeafNodes(TreeNode* root, int target) {
bool changed = true;
while (changed) {
changed = removeLeaves(root, nullptr, true, target);
if (!root->left && !root->right && root->val == target) {
return nullptr;
}
}
return root;
}
};class Solution:
def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
changed = True
while changed:
changed = False
def remove_leaves(node, parent, is_left):
nonlocal changed
if not node:
return
remove_leaves(node.left, node, True)
remove_leaves(node.right, node, False)
if not node.left and not node.right and node.val == target:
if parent:
if is_left:
parent.left = None
else:
parent.right = None
changed = True
remove_leaves(root, None, True)
if not root.left and not root.right and root.val == target:
return None
return rootclass Solution {
private boolean changed;
public TreeNode removeLeafNodes(TreeNode root, int target) {
changed = true;
while (changed) {
changed = false;
removeLeaves(root, null, true, target);
if (root.left == null && root.right == null && root.val == target) {
return null;
}
}
return root;
}
private void removeLeaves(TreeNode node, TreeNode parent, boolean isLeft, int target) {
if (node == null) return;
removeLeaves(node.left, node, true, target);
removeLeaves(node.right, node, false, target);
if (node.left == null && node.right == null && node.val == target) {
if (parent != null) {
if (isLeft) parent.left = null;
else parent.right = null;
}
changed = true;
}
}
}Complexity Analysis
Time Complexity: O(n × h) in the worst case, where n is the number of nodes and h is the height of the tree.
In the worst case, each pass removes only one leaf at the deepest level, and the cascading effect means we need up to h passes. Each pass traverses all remaining nodes (up to n). For a skewed tree (h = n), this becomes O(n²).
Space Complexity: O(h)
The recursion stack depth equals the height of the tree. In the worst case (skewed tree), this is O(n). For a balanced tree, it is O(log n).
Why This Approach Is Not Efficient
The brute force approach requires multiple full passes over the tree. In the worst case, consider a tree that is a single chain of nodes all with the target value: 1 → 2 → 2 → 2 → ... → 2. We can only remove one leaf per pass, leading to O(n) passes, each scanning up to O(n) nodes, for a total of O(n²) time.
The key insight is that we are doing redundant work. When we process children before parents (post-order), by the time we check a parent node, we already know whether its children survived. If we process the tree bottom-up in a single traversal, we can handle the cascading deletion naturally — a parent becomes a leaf during the same traversal if both its children were removed. This eliminates the need for multiple passes entirely.
Optimal Approach - Post-Order DFS (Single Pass)
Intuition
The crucial observation is that post-order traversal (left → right → node) naturally processes children before their parent. This means that by the time we evaluate a node, we have already decided whether to keep or remove its children.
If both children of a node have been removed (or were null to begin with), that node is now a leaf. If its value equals the target, we should remove it too — and we can do this immediately, in the same single traversal.
Think of it like pruning a real tree from the tips inward. You start at the outermost leaves and work your way toward the trunk. If you cut a leaf branch and the branch it was attached to is now bare and marked for removal, you cut that too — all in one sweep.
The recursive function returns the modified subtree: either the original node (if kept) or null (if removed). The parent simply sets its child pointer to whatever the recursive call returns.
Step-by-Step Explanation
Let's trace through Example 1: root = [1, 2, 3, 2, null, 2, 4], target = 2.
Tree:
1
/ \
2 3
/ / \
2 2 4
We use post-order DFS: process left subtree, then right subtree, then current node.
Step 1: Call dfs(node=2, leftmost leaf). It has no children → it is a leaf. Value 2 = target → return null.
Step 2: Back at node 2 (left child of root). Its left child returned null. It has no right child. Now node 2 has no children — it has become a leaf. Value 2 = target → return null.
Step 3: Call dfs(node=2, left child of node 3). No children → leaf. Value 2 = target → return null.
Step 4: Call dfs(node=4, right child of node 3). No children → leaf. Value 4 ≠ target → return node 4 (keep it).
Step 5: Back at node 3. Its left child returned null, right child returned node 4. Node 3 still has a child (node 4), so it is NOT a leaf → return node 3.
Step 6: Back at root node 1. Its left child returned null (the entire left subtree was pruned). Right child returned node 3. Node 1 still has a child → return node 1.
Result: The tree is now: 1 → 3 → 4 (right chain). Output: [1, null, 3, null, 4].
Notice how the cascading deletion happened naturally: node 2 (left-left) was removed, which made node 2 (left child of root) a leaf, which was then removed — all within one single traversal.
Post-Order DFS — Single-Pass Cascading Leaf Deletion — Watch how post-order traversal naturally handles cascading deletions: children are processed first, so parents know immediately if they have become leaves.
Algorithm
- Define a recursive function
dfs(node)that returns the modified subtree rooted atnode:
a. Ifnodeis null, return null (base case)
b. Recursively process the left child:node.left = dfs(node.left)
c. Recursively process the right child:node.right = dfs(node.right)
d. After processing children, check: ifnodeis now a leaf (both children are null) ANDnode.val == target, return null (remove this node)
e. Otherwise, returnnode(keep it) - Call
dfs(root)and return the result
Code
class Solution {
public:
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;
}
};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 rootclass 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;
}
}Complexity Analysis
Time Complexity: O(n)
We visit every node in the tree exactly once during the post-order DFS. At each node, we perform O(1) work: checking if it is a leaf and comparing its value to the target. Therefore, the total time is proportional to the number of nodes, which is O(n).
Space Complexity: O(h)
The space is dominated by the recursion call stack. In the worst case (a completely skewed tree where every node has only one child), the height h equals n, giving O(n) space. For a balanced binary tree, h = log n, so the space is O(log n).