Delete Leaves With a Given Value — Problem & Solution
Delete Leaves With a Given Value solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Delete Leaves With a Given Value is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree and an integer target, delete every leaf (a node with no children) whose value is target.
Deleting leaves can turn their parent into a leaf; if that parent's value is also target, it must be deleted too. Keep going until no leaf with value target remains, and return the root of what is left (the empty tree [] if everything was deleted).
Example 1
Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation: The leaves 2 go first; that leaves the left 2 a leaf too, so it goes as well. 1, 3 and 4 remain.
Example 2
Input: root = [1,3,3,3,2], target = 3
Output: [1,3,null,null,2]
Explanation: Only the leaf 3 under the left 3 and the right leaf 3 are removed; the left 3 still has the child 2.
Example 3
Input: root = [1,2,null,2,null,2], target = 2
Output: [1]
Explanation: The chain of 2s disappears one leaf at a time, leaving just the root.
Example 4
Input: root = [1,1,1], target = 1
Output: []
Explanation: Once both leaves go the root is a leaf with the target value, so the whole tree is deleted.
Constraints
1 <= number of nodes <= 30001 <= Node.val, target <= 1000
Hints for Delete Leaves With a Given Value
Hint 1
Whether a node becomes a removable leaf depends on what happens to its children first.
Hint 2
So process children before their parent — a post-order walk.
Hint 3
After pruning both subtrees, if the node now has no children and holds
target, return null in its place; otherwise return the node.
How to solve Delete Leaves With a Given Value
A post-order walk settles each subtree before looking at its root, so by the time a node is examined its children have already been deleted if they had to be — one pass does all the cascading.
Approach
- If the node is null, return null.
- Replace its left child by the result of processing the left subtree, and the same on the right.
- If the node now has no children and its value equals
target, return null; otherwise return the node. - The value returned for the root is the answer.
Why it works
When the walk returns from a node, that node's subtree contains no leaf equal to target: its children's subtrees were cleaned first, and the node itself is removed exactly when it has become such a leaf. A node that still has a child can never be removed later, because its subtree is final.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion
Pitfalls
- Checking a node before its children (pre-order) misses parents that only become leaves afterwards.
- The root itself can disappear, giving the empty tree.
Reference solution
Python
from typing import Optional
def removeLeafNodes(root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
if root is None:
return None
root.left = removeLeafNodes(root.left, target)
root.right = removeLeafNodes(root.right, target)
if root.left is None and root.right is None and root.val == target:
return None
return rootJava
public static 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;
}C++
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;
}JavaScript
var removeLeafNodes = function(root, 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;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals