Abstract / Summary

Remove a given node from a binary search tree while keeping it a valid binary search tree.

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 55% (1+ million submissions).

Typical patterns to solve this problem:

• Binary Search Tree
• 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 removes a node with a given key from a binary search tree (BST) while preserving the BST ordering properties. It follows a recursive strategy that first locates the target node, then restructures the tree based on the number of children the node possesses. The algorithm handles empty trees, missing keys, leaf nodes, nodes with a single child, and nodes with two children, ensuring a correct and efficient re-linking of the remaining sub-trees.

Key Steps

Base case for an empty subtree

When the recursion reaches a null reference, the function returns None, indicating that the key does not exist in that branch.

if not root:
    return None

Traversal to locate the node

The BST property allows a directed search: if the current node’s value is greater than the key, the algorithm recurses into the left subtree; if it is smaller, it recurses into the right subtree. After the recursive call, the current node is returned unchanged, preserving the link to its parent.

if root.val > key:
    root.left = self.deleteNode(root.left, key)
    return root
if root.val < key:
    root.right = self.deleteNode(root.right, key)
    return root

Deleting a node with a single child

If the node to delete has no left child, the function returns its right child, effectively bypassing the node. Conversely, if there is no right child, the left child is returned. This handles leaf nodes as a special case of a single-child scenario because both children are None.

if not root.left:
    return root.right
if not root.right:
    return root.left

Deleting a node with two children

When both children exist, the algorithm selects the predecessor (the largest value in the left subtree) to replace the deleted node’s value. It walks down the left child and then repeatedly follows right pointers until the rightmost node is found. The predecessor’s value is copied to the current node, and the predecessor itself is removed by linking its parent directly to its left child (which may be None). This maintains the BST invariant without creating new nodes.

up = root
next = up.left
while next.right:
    up = next
    next = next.right

root.val = next.val

if up == root:
    up.left = next.left
else:
    up.right = next.left

Returning the restructured subtree

After handling the appropriate case, the function returns the (potentially modified) root of the current subtree, allowing the recursion to rebuild the full tree with the deleted node omitted.

return root

Edge Cases Handled

The code gracefully deals with an empty input tree by immediately returning None. If the key is not present, the recursive descent reaches a null child and returns None, which propagates without altering the existing structure. When the node to delete is a leaf, both child checks evaluate to True, and the function returns None, effectively pruning the leaf. The case where the node to delete is the root is covered by the same logic; the root reference is updated in place or replaced by its child, preserving the external reference to the tree’s new root. For a node with two children, the algorithm correctly handles the situation where the predecessor is the immediate left child (i.e., the left subtree has no right descendants) by checking whether up still points to the original node and adjusting the left link accordingly.

Performance Optimizations

The implementation leverages the BST ordering to limit traversal to a single path from the root to the target node, avoiding unnecessary scans of unrelated branches. By using recursion with early returns after each directional move, the function minimizes the number of stack frames and ensures that only the relevant subtree is processed. The predecessor search stops as soon as the rightmost node in the left subtree is found, which is the minimal work required to locate the replacement value. Moreover, the code reuses existing node objects; it never creates new TreeNode instances, thereby reducing allocation overhead and keeping memory usage low. The direct reassignment of child pointers (up.left = next.left or up.right = next.left) eliminates the need for additional temporary structures, resulting in a concise and efficient in-place modification of the tree.

Imagine a big family tree made of numbers. Each number lives in a little house, and every house has a door to the left for smaller numbers and a door to the right for bigger numbers. When you want to remove a specific number, you first go on a treasure hunt to find the house where that number lives. You look at the number in the current house and, if the number you are looking for is smaller, you peek through the left door. If it is bigger, you peek through the right door. You keep doing this until you find the right house.

Once the house is found, there are a few ways to take the number away. If the house has no other houses connected to it, you simply close its door and it leaves. If there is only one house connected to it, that house gets promoted to take its place.

If there are two houses connected to it, things get a bit busy. You look inside the left door and go as far to the right as possible to find the biggest number that is still smaller than the one you are removing. You swap that special number into the house you are emptying. Then, you clean up the old spot where that number was hiding to make sure everything stays connected properly.

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

not analyzed yet

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			Rust				Go	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai			Java
	everthis				JS
	fartem							Ruby
	FelixFan1122			Java
	fengvyi	C++
	haoel		Python
	JoshCrozier				JS
	keineahnung2345	C++
	Krazune	C++
	linouk23	C++
	lkwq007		Python
	ruoru						Rust
	suxrobGM					C#
	trung-hn		Python
	varunu28			Java
	vli02									C
	wisdompeak	C++
	XiaotaoGuo	C++
	yuanliu666								Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
FelixFan1122	Java
fengvyi	C++
haoel	Python
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
linouk23	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
wisdompeak	C++
XiaotaoGuo	C++
yuanliu666	Kotlin
YuriSpiridonov	Python
zfang399	C++

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