Delete Leaves With a Given Value solution and explanation
Google
9 more videos on this problem
Delete Leaves With a Given Value - Leetcode 1325 - PythonNeetCodeIO · 14:45 · 10K views
Delete Leaves With a Given Value | Simple Story To Code | Leetcode 1325 | codestorywithMIKcodestorywithMIK · 12:42 · 7K views
1325. Delete Leaves With a Given Value | DFS | RecursionAryan Mittal · 9:43 · 1K views
1325. Delete Leaves With a Given Value | Leetcode MediumJOY of LIFE · 17:51 · 911 views
Delete Leaves With a Given Value (Leetcode 1325)Coding Interviews · 9:31 · 873 views
Leetcode Solution - 1325 Delete Leaves With a Given ValueJohn Leonardo · 4:10 · 706 views
1325. Delete Leaves With a Given Value - English VersionSimple Code - 단순코드 · 6:13 · 254 views
[LeetCode] 1325. Delete Leaves With a Given Value개발자영맨(bluedawnstar) · 14:01 · 180 views
Leetcode 1325. Delete Leaves With a Given ValueJeevan Kumar - Cracckify · 4:54 · 98 views
Delete Leaves With a Given Value || Leetcode 1325Sivasairam Degala · 4:32 · 97 views
The problem
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
Approach overview
Problem Overview: Given the root of a binary tree and a target value, remove every leaf node whose value equals the target. After deleting a leaf, its parent might become a new leaf that also matches the target, so the process continues until no such leaves remain.
Approach 1: Recursive Depth-First Search (Post-Order DFS) (Time: O(n), Space: O(h))
The cleanest solution uses depth-first search with a post-order traversal. Traverse to the left and right children first, then evaluate the current node. After recursion returns, check whether both children are null and the node value equals the target. If so, return null to the parent, effectively deleting the node.
The key insight: a node can only become a removable leaf after its children are processed. Post-order traversal guarantees that children are handled before their parent. Each node is visited once, so the total work is linear. The recursion stack grows proportional to the tree height h, which is O(log n) for balanced trees and O(n) in the worst case.
This approach works naturally with recursive tree processing and is commonly used in tree and binary tree problems where parent decisions depend on child results.
Approach 2: Iterative Post-Order Traversal (Time: O(n), Space: O(n))
An iterative solution simulates post-order traversal using an explicit stack. Push nodes while traversing down the tree and track whether the node has already visited its children. When both children have been processed, evaluate whether the node is now a leaf with the target value.
If the node should be deleted, update its parent pointer in the stack structure to remove the reference. This approach mirrors the recursive logic but manages traversal state manually. The main advantage is avoiding recursion limits in languages or environments where stack depth could be large.
Because every node is pushed and processed once, the traversal still runs in O(n) time. The explicit stack can hold up to O(n) nodes in skewed trees.
Recommended for interviews: Recursive DFS with post-order traversal. It expresses the core idea directly: process children first, then decide whether the current node becomes a removable leaf. Showing the recursive version demonstrates strong understanding of tree recursion. The iterative version is useful when interviewers specifically ask for a non-recursive traversal or stack-based implementation.
Approach 1: Recursive Depth-First Search (DFS)
This approach involves using a recursive DFS to navigate through the binary tree. We start from the root and check the leaf nodes. If a leaf node matches the target value, we remove it by returning null; otherwise, return the node itself. This should also be applied recursively to handle cases where removing a leaf creates another leaf node which must also be removed.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def removeLeafNodes(root, target):
if not root:
return None
root.left = removeLeafNodes(root.left, target)
root.right = removeLeafNodes(root.right, target)
if not root.left and not root.right and root.val == target:
return None
return rootclass 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;
}
}struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
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) {
delete root;
return nullptr;
}
return root;
}
};In this solution, we recursively dive into the left and right subtrees to remove the leaf nodes with the target value. After modifying both subtrees, we check if the current node has become a leaf with the target value and delete it if so.
Time Complexity: O(n), where n is the number of nodes in the tree, since we visit each node exactly once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack.
Approach 2: Iterative Post-Order Traversal
This approach uses an iterative post-order traversal to visit the nodes of the binary tree. By using a stack, we can simulate the recursive process, ensuring we evaluate and remove leaf nodes correctly by visiting left, right, and then parent nodes.
function TreeNode(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
function removeLeafNodes(root, target) {
let dummy = new TreeNode(-1);
dummy.left = root;
const stack = [[dummy, null]];
while (stack.length) {
const [node, dir] = stack.pop();
if (node.left) stack.push([node.left, 'left']);
if (node.right) stack.push([node.right, 'right']);
if (dir) {
let child = node[dir];
if (!child.left && !child.right && child.val === target) {
node[dir] = null;
}
}
}
return dummy.left;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public 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;
}
}This JavaScript solution uses an iterative approach to simulate the post-order traversal. By attaching a dummy node to facilitate handling the root node, each node and its corresponding direction (left/right) are pushed onto a stack. As nodes are processed, if a node matches the target and is a leaf, it is removed by setting its parent's pointer to null.
Time Complexity: O(n), each node is visited once.
Space Complexity: O(h), where h is the height of the tree, required for the stack.
Approach 3: Default Approach
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function removeLeafNodes(root: TreeNode | null, target: number): TreeNode | null {
if (!root) {
return null;
}
root.left = removeLeafNodes(root.left, target);
root.right = removeLeafNodes(root.right, target);
if (!root.left && !root.right && root.val == target) {
return null;
}
return root;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func removeLeafNodes(root *TreeNode, target int) *TreeNode {
if root == nil {
return nil
}
root.Left = removeLeafNodes(root.Left, target)
root.Right = removeLeafNodes(root.Right, target)
if root.Left == nil && root.Right == nil && root.Val == target {
return nil
}
return root
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search (DFS) | Time Complexity: O(n), where n is the number of nodes in the tree, since we visit each node exactly once. |
| Iterative Post-Order Traversal | Time Complexity: O(n), each node is visited once. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search (Post-Order) | O(n) | O(h) | Best general solution. Simple logic when using recursion on binary trees. |
| Iterative Post-Order Traversal | O(n) | O(n) | Useful when recursion depth could be large or when an interviewer asks for an iterative traversal. |
Frequently asked questions
Is Delete Leaves With a Given Value easy or hard?
The problem is classified as Medium on LeetCode. The main difficulty comes from recognizing that nodes may become removable leaves after their children are deleted, which requires a post-order traversal rather than a simple single-pass check.
Delete Leaves With a Given Value Python/Java solution
In Python or Java, implement a recursive function that returns the updated subtree root. Call the function on left and right children first, assign the returned nodes back to the current node, and then check if the node became a leaf with the target value. If so, return null; otherwise return the node.
How to solve Delete Leaves With a Given Value in O(n)?
Use a post-order DFS traversal. Recursively process the left and right children, then check if the current node has become a leaf and its value equals the target. If both conditions hold, return null so the parent removes that node. Since each node is processed once, the total runtime is O(n).
What is the best approach for Delete Leaves With a Given Value?
The best approach is a post-order Depth-First Search. Traverse the left and right subtrees first, then check if the current node became a leaf with the target value. If both children are null and the value equals the target, return null to delete the node. This solution runs in O(n) time and O(h) space where h is the tree height.
Is Delete Leaves With a Given Value asked at Google/Amazon/Meta?
Binary tree pruning and post-order DFS patterns like this appear frequently in interviews at companies such as Amazon, Google, and Meta. Variants include removing nodes based on subtree conditions or evaluating nodes after processing children. Practicing this problem builds strong intuition for recursive tree processing.
What data structure is used in Delete Leaves With a Given Value?
The problem operates on a binary tree and is typically solved using Depth-First Search. The algorithm relies on recursion or an explicit stack to perform post-order traversal so that nodes are evaluated after their children.
What is the time complexity of Delete Leaves With a Given Value?
The optimal solution runs in O(n) time because every node in the binary tree is visited exactly once during the DFS traversal. Each node performs constant work when checking its children and value. The space complexity is O(h) due to the recursion stack, where h is the tree height.