BST Delete: Three Cases
Handle leaf deletion, single-child deletion, and two-child deletion using the in-order successor, implementing the algorithm from scratch.
BST Delete: Three Cases is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Why BST Deletion is Tricky
BST deletion is the most complex of the three core operations because removing a node must preserve the BST property for the entire tree. There are three distinct cases depending on the node's children: it has no children (leaf), one child, or two children. Each case requires a different strategy. Interviewers love this problem because it tests pointer manipulation, edge-case thinking, and knowledge of the in-order successor concept.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Three cases for deleting a node:
# Case 1: Leaf node (no children) -> simply remove it
# Case 2: One child -> replace node with its child
# Case 3: Two children -> replace value with in-order successor
# then delete the in-order successor
print('BST delete: 3 cases based on number of children')Case 1: Deleting a Leaf Node
A leaf node has no children. Deletion is simple: return None from the recursive call, which causes the parent to set its pointer (left or right) to null. This is the base case that all BST delete implementations must handle first. Verify this works for the special case where the tree has only one node (the root is a leaf).
def find_min(node):
while node.left:
node = node.left
return node
# Demonstrating leaf deletion:
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.left = TreeNode(1) # leaf
root.left.right = TreeNode(4) # leaf
# To delete node 1 (leaf): set root.left.left = None
root.left.left = None
print(root.left.left) # None -- deleted
print(root.left.val) # 3 still intactCase 2: Node with One Child
When a node has exactly one child, replace the node with that child. Return the non-null child from the recursive call so the parent's pointer is updated to skip over the deleted node. This works seamlessly whether the single child is on the left or the right — just return whichever one exists.
# Demonstrating one-child deletion:
# Tree: 5
# / \
# 3 7
# \
# 4
# Delete node 3 (has only right child 4):
# Result: 5
# / \
# 4 7
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.right = TreeNode(4)
# In the recursive implementation:
# When we reach node 3 and it has no left child,
# we return root.right (node 4) to the parent.
# Parent sets its left pointer to 4, skipping 3.
print('One-child case: return the surviving child')Case 3: Node with Two Children
When a node has two children, we cannot simply remove it. Instead, find the node's in-order successor (the smallest value in the right subtree), copy its value into the current node, then delete the in-order successor from the right subtree. The successor has at most one child (no left child), so deleting it falls into Case 1 or Case 2 — which we already know how to handle.
# Demonstrating two-child deletion:
# Tree: 5
# / \
# 3 7
# / \
# 6 9
# Delete node 5 (two children 3 and 7):
# In-order successor = 6 (smallest in right subtree)
# Step 1: replace 5's value with 6
# Step 2: delete 6 from right subtree
# Result: 6
# / \
# 3 7
# \
# 9
print('Two-child case: replace with in-order successor')Complete BST Delete Implementation
The full recursive delete combines all three cases. Find the node to delete by comparing values, then handle the appropriate case. The pattern of returning the (possibly modified) root at each level and assigning it back to root.left or root.right elegantly handles all pointer updates without explicit parent tracking. Time complexity is O(h).
def delete_node(root, key):
if not root:
return None # key not found
if key < root.val:
root.left = delete_node(root.left, key)
elif key > root.val:
root.right = delete_node(root.right, key)
else: # found the node to delete
if not root.left: # Case 1 or 2: no left child
return root.right
if not root.right: # Case 2: no right child
return root.left
# Case 3: two children -> find in-order successor
successor = find_min(root.right)
root.val = successor.val # copy successor value up
root.right = delete_node(root.right, successor.val) # delete successor
return root
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
root = delete_node(root, 5)
print(root.val) # 6 (successor replaced 5)Why the In-Order Successor?
The in-order successor (minimum of the right subtree) is used instead of the maximum of the left subtree because both are valid choices — using either preserves BST property. The in-order predecessor (maximum of left subtree) also works. Some implementations alternate to keep the tree balanced. In interviews, the in-order successor version is more commonly expected; mention that the predecessor works equally well.
# Both approaches are valid for two-child deletion:
# Option A: Replace with in-order SUCCESSOR (min of right subtree)
# - Successor goes to current position
# - Delete successor from right subtree
# Option B: Replace with in-order PREDECESSOR (max of left subtree)
# - Predecessor goes to current position
# - Delete predecessor from left subtree
def find_max(node):
while node.right:
node = node.right
return node
# Using predecessor:
def delete_node_pred(root, key):
if not root:
return None
if key < root.val:
root.left = delete_node_pred(root.left, key)
elif key > root.val:
root.right = delete_node_pred(root.right, key)
else:
if not root.left:
return root.right
if not root.right:
return root.left
pred = find_max(root.left)
root.val = pred.val
root.left = delete_node_pred(root.left, pred.val)
return root
print('Both successor and predecessor deletion are correct')Deleting All Nodes with a Value
A variation asks you to delete all nodes with values within a range or matching a condition. For a BST, this is efficient: recurse into the appropriate subtree based on comparisons, applying the delete operation wherever the condition matches. The recursive structure of BST delete naturally extends to these scenarios without requiring a separate traversal pass.
# Delete all nodes with values outside [low, high]
def trim_bst(root, low, high):
if not root:
return None
if root.val < low:
# Entire left subtree is also < low, skip to right
return trim_bst(root.right, low, high)
if root.val > high:
# Entire right subtree is also > high, skip to left
return trim_bst(root.left, low, high)
# Current node is within range
root.left = trim_bst(root.left, low, high)
root.right = trim_bst(root.right, low, high)
return root
root = TreeNode(3)
root.left = TreeNode(0)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
root.left.right.left = TreeNode(1)
root = trim_bst(root, 1, 3)
print(root.val, root.left.val) # 3 2BST Iterator Pattern
The BST iterator (LeetCode #173) returns elements in sorted order one at a time, with O(1) average time and O(h) space. Implement it with a stack that simulates the iterative in-order traversal: on construction, push all left nodes from the root. On next(), pop the top, push all left nodes of the right subtree. This is a controlled unrolling of the iterative in-order algorithm.
class BSTIterator:
def __init__(self, root):
self.stack = []
self._push_left(root)
def _push_left(self, node):
while node:
self.stack.append(node)
node = node.left
def next(self):
node = self.stack.pop()
if node.right:
self._push_left(node.right)
return node.val
def has_next(self):
return bool(self.stack)
root = TreeNode(7)
root.left = TreeNode(3)
root.right = TreeNode(15)
root.right.left = TreeNode(9)
it = BSTIterator(root)
while it.has_next():
print(it.next(), end=' ') # 3 7 9 15Delete Node: Complexity Analysis
BST delete runs in O(h) time where h is the tree height. For a balanced BST, this is O(log n). For a skewed tree, it degrades to O(n). Finding the in-order successor adds at most one extra O(h) traversal of the right subtree, which does not change the overall complexity. Space complexity is O(h) for the call stack in the recursive implementation.
# Complexity summary for BST operations:
# Operation | Balanced | Skewed
# ----------|-----------|-------
# Search | O(log n) | O(n)
# Insert | O(log n) | O(n)
# Delete | O(log n) | O(n)
# Min/Max | O(log n) | O(n)
# In-order | O(n) | O(n) (visits all nodes)
# The key: BST guarantees these complexities only when balanced.
# Python standard library has no balanced BST.
# Use sortedcontainers.SortedList for O(log n) ops in practice.
print('All BST core ops are O(h): O(log n) balanced, O(n) skewed')Two Sum in BST
Two Sum IV in a BST asks whether any two nodes sum to a target. One approach uses a set: in-order traversal collects values while checking if target - current exists in the set so far. A more elegant approach uses a BST iterator forward and a BST iterator backward simultaneously (like two pointers) — this avoids extra space beyond O(h) for each iterator's stack.
def find_target_bst(root, k):
seen = set()
def inorder(node):
if not node:
return False
if inorder(node.left):
return True
if k - node.val in seen:
return True
seen.add(node.val)
return inorder(node.right)
return inorder(root)
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.right.right = TreeNode(7)
print(find_target_bst(root, 9)) # True (2+7)
print(find_target_bst(root, 28)) # FalseConvert BST to Greater Sum Tree
The greater sum tree (LeetCode #538) replaces each node's value with the sum of all values greater than or equal to it in the BST. The key insight: do a reverse in-order traversal (right → root → left) to visit nodes in decreasing order and accumulate a running sum. This runs in O(n) time and O(h) space.
def bst_to_gst(root):
acc = [0] # running accumulated sum
def reverse_inorder(node):
if not node:
return
reverse_inorder(node.right) # visit larger values first
acc[0] += node.val
node.val = acc[0] # replace with cumulative sum
reverse_inorder(node.left)
reverse_inorder(root)
return root
root = TreeNode(4)
root.left = TreeNode(1)
root.right = TreeNode(6)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
bst_to_gst(root)
print(root.val) # 4+5+6+7 = 22
print(root.right.val) # 5+6+7 = 18Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: three BST deletion cases (leaf, one child, two children), the in-order successor technique for two-child deletion, and clean recursive patterns like BST iterator and BST-to-greater-sum tree. Next up we validate BST correctness and leverage in-order properties.
Frequently asked questions
Is the “BST Delete: Three Cases” lesson free?
Yes — the full text of “BST Delete: Three Cases” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “BST Delete: Three Cases”?
Handle leaf deletion, single-child deletion, and two-child deletion using the in-order successor, implementing the algorithm from scratch. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “BST Delete: Three Cases” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.