Skip to main content
Talentd

Delete Leaves With a Given Value - Solution & Explanation

MediumTreeDepth-First SearchBinary Tree10 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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.

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.

Code

PythonJavaC++

Python

Java

C++

Complexity

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.

Try this approach in the editor →

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.

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.

Code

JavaScriptC#

JavaScript

C#

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack.

Iterative Post-Order Traversal

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.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 TraversalO(n)O(n)Useful when recursion depth could be large or when an interviewer asks for an iterative traversal.

Video Solution

Delete Leaves With a Given Value - Leetcode 1325 - Python • NeetCodeIO • 10,931 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Delete Leaves With a Given Value with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Unique Binary Search Trees II