Abstract / Summary

Remove all leaf nodes with a given value repeatedly until no more exist.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 77% (300k+ submissions).

Typical patterns to solve this problem:

• Binary Tree
• Depth First Search
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a method removeLeafNodes that removes all leaf nodes whose value equals a given target. The algorithm works recursively, traversing the tree from the root toward the leaves, deciding for each node whether it should be pruned after its children have been processed. The method returns the possibly modified root, or None when the entire tree is eliminated.

Key Steps

The core of the algorithm is the nested helper function deeper. Its purpose is to determine, for a given node, whether the subtree rooted at that node should be removed entirely. The function returns a Boolean flag: True indicates that the node is a leaf with the target value (or has become such after its children are removed), and therefore the caller should delete the reference to this node.

def deeper(node):  # True if leaf that should be deleted
    if not node:
        return True

The first conditional treats a None reference as a trivially removable subtree. This convention simplifies the logic for parent nodes, allowing them to treat missing children uniformly.

The next two lines perform a post-order traversal, recursively evaluating the left and right subtrees before any decision is made about the current node.

    l = deeper(node.left)
    r = deeper(node.right)

After the recursive calls return, the algorithm checks the flags l and r. If a flag is True, the corresponding child is a leaf that matches the target and must be detached from the current node.

    # delete children
    if l:
        node.left = None
    if r:
        node.right = None

Finally, the function decides whether the current node itself qualifies for removal. The node is removed only when its value equals target and both of its children have been removed (or were originally absent). This condition ensures that only leaf nodes are eliminated, while internal nodes are retained unless they become leaves after their children are pruned.

    return node.val == target and l and r

The outer method invokes deeper on the original root and interprets the returned flag to decide whether the root itself should be discarded.

return None if deeper(root) else root

Edge Cases Handled

When the input root is None, the helper receives a None node, immediately returns True, and the outer method consequently returns None. This covers the empty-tree scenario without additional checks.

If a leaf node’s value does not match target, the helper returns False for that leaf, leaving the node intact. The parent’s logic will not delete the child because the flag is False.

When a non-leaf node’s children are all removed because they matched the target, the node may become a leaf. The final return statement of deeper evaluates the node’s value against target together with the flags for both children. If the node’s value also matches target, the node is removed; otherwise it remains as a new leaf. This cascading effect correctly handles cases where removal of deeper leaves turns ancestors into removable leaves.

The early-return for None nodes also ensures that the algorithm does not attempt to access attributes of a missing child, preventing attribute-access errors in deep recursion.

Performance Optimizations

The algorithm operates in a single depth-first pass, visiting each node exactly once. By performing the removal of child references immediately after the recursive calls, it avoids the need for a second traversal to clean up dangling pointers. This in-place modification reduces memory overhead because no auxiliary data structures (such as stacks or lists) are allocated to track nodes slated for deletion.

The use of a Boolean return value to signal deletability eliminates the need for constructing explicit node objects to represent “removed” subtrees. The parent node can directly set its child pointer to None based on the flag, which is a constant-time operation.

Because the recursion is tail-recursive only for the base case (None), the call stack depth corresponds to the height of the tree. No additional recursion depth is introduced by auxiliary processing, keeping the stack usage minimal for balanced trees.

Overall, the design leverages the natural recursion of binary trees to achieve an efficient, in-place pruning process without extra passes or data structures.

Imagine a tree made of light where every dot is a lightbulb. Some bulbs have the same number written on them. A leaf is a bulb at the very end of a branch that has no other bulbs hanging below it.

This code starts at the top and travels all the way down to the bottom of the tree to find those lone end bulbs. It checks if the number on an end bulb matches the target number. If it does, the code snips that bulb off the branch. Once a bulb is gone, a branch that had a bulb might suddenly become an end branch itself. The code is smart enough to look again and nip off those new ends if they also match the target number. It keeps looking until all the matching end bulbs are gone.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python			Java			TS
	WalkCCC	C++	Python			Java
	leetcode.ca	C++	Python			Java		Go	TS
	Progiez	C++	Python			Java
github	BigEggStudy			C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai					Java
	everthis				JS
	fartem						Ruby
	fpdjsns	C++
	fsq	C++
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007		Python
	lzl124631x	C++
	shreymehul			C#
	suxrobGM			C#
	trung-hn		Python
	varunu28					Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fpdjsns	C++
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
shreymehul	C#
suxrobGM	C#
trung-hn	Python
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality