Delete Leaves With a Given Value

Med

#1232Time: 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).

Algorithms

Depth-First Search

Data structures

Tree Binary Tree

Prompt

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 target value.
If a child is a leaf to be deleted, set the corresponding child pointer (left or right) to null.
Keep a flag to track if any node was deleted in the current pass.
If the flag is false after 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.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode removeLeafNodes(TreeNode root, int target) {18        // A dummy root helps simplify parent tracking for the actual root.19        TreeNode dummy = new TreeNode(0);20        dummy.left = root;21 22        boolean changed = true;23        while (changed) {24            // We assume no changes will be made in this pass initially.25            changed = false;26            if (scanAndRemove(dummy, target)) {27                changed = true;28            }29        }30        return dummy.left;31    }32 33    // Scans the tree once and removes current leaves with the target value.34    // Returns true if at least one node was removed.35    private boolean scanAndRemove(TreeNode node, int target) {36        if (node == null) {37            return false;38        }39 40        boolean deleted = false;41        // Check left child42        if (node.left != null && node.left.left == null && node.left.right == null && node.left.val == target) {43            node.left = null;44            deleted = true;45        }46        // Check right child47        if (node.right != null && node.right.left == null && node.right.right == null && node.right.val == target) {48            node.right = null;49            deleted = true;50        }51 52        // Recurse and combine results53        boolean leftChanged = scanAndRemove(node.left, target);54        boolean rightChanged = scanAndRemove(node.right, target);55 56        return deleted || leftChanged || rightChanged;57    }58}

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.

This optimal solution leverages a single post-order traversal. A post-order traversal (Left-Right-Node) ensures that when we visit a node, its left and right subtrees have already been processed and pruned. This allows us to check if the current node has become a leaf with the target value and decide whether to delete it, all within one pass.

Algorithm

Define a recursive function removeLeafNodes(node, target) that returns a TreeNode.
Base Case: If node is null, return null.
Recursive Step (Post-order):
- Call removeLeafNodes on the left child: node.left = removeLeafNodes(node.left, target).
- Call removeLeafNodes on the right child: node.right = removeLeafNodes(node.right, target).
Process Node:
- After the children have been processed, check if the current node is a leaf (node.left == null && node.right == null) and if node.val == target.
- If both conditions are true, return null to remove the node.
- Otherwise, return the node itself.
The initial call is removeLeafNodes(root, target), and its result is the new root of the final tree.

Walkthrough

The function recursively calls itself on its children first. The return value of the recursive call is the new root of the processed subtree, which could be null if the entire subtree was deleted. The parent node then updates its child pointers with these return values.

After the recursive calls for the left and right children return, we examine the current node. Because its children may have been removed, the current node might now be a leaf. If it is a leaf and its value matches the target, the function returns null, effectively signaling its parent to delete it. Otherwise, it returns the node itself.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode removeLeafNodes(TreeNode root, int target) {18        // Base case: if the node is null, there's nothing to do.19        if (root == null) {20            return null;21        }22 23        // 1. Recurse on the left and right children first (Post-order).24        // Update the children with the result of the recursive call.25        root.left = removeLeafNodes(root.left, target);26        root.right = removeLeafNodes(root.right, target);27 28        // 2. Process the current node.29        // Check if it has become a leaf node with the target value.30        if (root.left == null && root.right == null && root.val == target) {31            // This node needs to be deleted. Return null to its parent.32            return null;33        }34 35        // If the node is not a leaf to be deleted, return it.36        return root;37    }38}

Complexity

Time

O(N), where N is the total number of nodes in the tree. Each node is visited and processed exactly once.

Space

O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a completely unbalanced (skewed) tree, H can be equal to N, making the space complexity O(N). For a balanced tree, it would be O(log N).

Trade-offs

Pros

Optimal time complexity of O(N).
Elegant, concise, and easy-to-read recursive solution.
Correctly handles the cascading deletion effect in a single pass.

Cons

For extremely deep trees, a recursive solution could potentially lead to a StackOverflowError. However, given the problem constraints (up to 3000 nodes), this is not a practical concern.

Solutions

Solution

1/** * 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 ; } }

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ 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 ; } };

1# 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 class Solution : def removeLeafNodes ( self , root : Optional [ TreeNode ], target : int ) -> Optional [ TreeNode ]: if root is None : return None root . left = self . removeLeafNodes ( root . left , target ) root . right = self . removeLeafNodes ( root . right , target ) if root . left is None and root . right is None and root . val == target : return None 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.

← Previous

Previous problem

Next problem