Delete Leaves With a Given Value - Video Solutions

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.