Delete Leaves With a Given Value
MedPrompt
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 target, it should also be deleted (you need to continue doing that until you cannot).
Example 1:
Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left).
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).Example 2:
Input: root = [1,3,3,3,2], target = 3
Output: [1,3,null,null,2]Example 3:
Input: root = [1,2,null,2,null,2], target = 2
Output: [1]
Explanation: Leaf nodes in green with value (target = 2) are removed at each step.
Constraints:
- The number of nodes in the tree is in the range
[1, 3000]. 1 <= Node.val, target <= 1000
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves repeatedly scanning the entire tree to find and remove leaf nodes that match the target value. This process is looped until a full scan of the tree results in no deletions. This ensures that any parent node that becomes a leaf after its children are removed is also considered for deletion in a subsequent pass.
Algorithm
- Create a loop that continues as long as changes are made to the tree in a pass.
- In each pass, traverse the tree from the root.
- For each node, check if its children are leaf nodes with the
targetvalue. - If a child is a leaf to be deleted, set the corresponding child pointer (
leftorright) tonull. - Keep a flag to track if any node was deleted in the current pass.
- If the flag is
falseafter a full pass, no more deletions are possible, so exit the loop. - Handle the edge case where the root itself becomes a leaf and needs to be deleted.
Walkthrough
The core idea is to simulate the cascading deletion by iterating. In each pass, we traverse the tree and remove all nodes that are currently leaves and have the value target. Since removing a leaf might cause its parent to become a new leaf with the target value, we must repeat the entire process. The loop terminates when a full traversal is completed without any nodes being removed.
This requires a traversal function that can modify the tree structure, which means it needs a reference to the parent of the node being considered for deletion.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public TreeNode removeLeafNodes(TreeNode root, int target) { // A dummy root helps simplify parent tracking for the actual root. TreeNode dummy = new TreeNode(0); dummy.left = root; boolean changed = true; while (changed) { // We assume no changes will be made in this pass initially. changed = false; if (scanAndRemove(dummy, target)) { changed = true; } } return dummy.left; } // Scans the tree once and removes current leaves with the target value. // Returns true if at least one node was removed. private boolean scanAndRemove(TreeNode node, int target) { if (node == null) { return false; } boolean deleted = false; // Check left child if (node.left != null && node.left.left == null && node.left.right == null && node.left.val == target) { node.left = null; deleted = true; } // Check right child if (node.right != null && node.right.left == null && node.right.right == null && node.right.val == target) { node.right = null; deleted = true; } // Recurse and combine results boolean leftChanged = scanAndRemove(node.left, target); boolean rightChanged = scanAndRemove(node.right, target); return deleted || leftChanged || rightChanged; }}Note: The provided code is a conceptual illustration of an iterative pass-based approach. The logic is slightly simplified for clarity.
Complexity
Time
O(N * H), where N is the number of nodes and H is the height of the tree. Each pass requires a full tree traversal (O(N)). In the worst-case scenario of a skewed tree, we might only remove one leaf per pass, requiring H passes. This leads to a total time complexity of O(N^2).
Space
O(H) for the recursion stack used by the traversal function in each pass. For a skewed tree, this can be O(N).
Trade-offs
Pros
The logic is straightforward: keep cleaning the tree until it's stable.
Cons
Very inefficient due to the need for multiple full traversals of the tree.
The implementation can be complex, especially handling parent pointers and the root node correctly.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class 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 ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.