Delete Node in a Binary Search Tree – LeetCode75 Python Solution Explained

The Delete Node in a Binary Search Tree (BST) problem (LeetCode75) is a classic BST challenge that tests your understanding of tree traversal, recursion, and node deletion cases. This problem is commonly asked in technical interviews and helps evaluate problem-solving skills when working with hierarchical data structures.

In this blog, we will break down the problem, provide examples, explain the Python solution step by step with code snippets, analyze time and space complexity, discuss edge cases and explore real-world applications.

Problem Statement

Given the root of a BST and an integer key, delete the node with value key and return the root of the updated BST.

When deleting a node, there are three main cases:

1. Node has no children → delete node directly.
2. Node has one child → replace node with its child.
3. Node has two children → replace node with inorder successor (smallest value in right subtree) or inorder predecessor (largest value in left subtree).

Complete Python Solution

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root:
            return root

        # Traverse left or right depending on the key
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
        else:
            # Node with only one child or no child
            if not root.left:
                return root.right
            if not root.right:
                return root.left

            # Node with two children: find inorder successor
            temp = root.right
            while temp.left:
                temp = temp.left
            root.val = temp.val
            root.right = self.deleteNode(root.right, root.val)

        return root

Step-by-Step Explanation

Step 1: Base Case

If the root is None, simply return None.

if not root:
    return root

Step 2: Traverse the Tree

• If key is less than root.val, search the left subtree.
• If key is greater than root.val, search the right subtree.

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

Step 3: Handle Deletion

Case 1: Node has no left child → replace with right child

if not root.left:
    return root.right

Case 2: Node has no right child → replace with left child

if not root.right:
    return root.left

Case 3: Node has two children → find inorder successor

temp = root.right
while temp.left:
    temp = temp.left
root.val = temp.val
root.right = self.deleteNode(root.right, root.val)

• Inorder successor ensures BST property is maintained.
• Recursively delete the successor node after copying its value.

Step 4: Return Updated Root

return root

Time and Space Complexity

• Time Complexity:O(h)
  • h = height of the tree
  • Balanced BST → O(log n)
  • Skewed BST → O(n)
• Space Complexity: O(h) due to recursion stack.

Edge Cases

1. Empty tree: return None.
2. Key not present: tree remains unchanged.
3. Node has no children: node is removed directly.
4. Node has one child: child replaces the node.
5. Node has two children: handled via inorder successor.

Real-World Applications

• Database Operations: Efficient deletion in indexed BST-based storage.
• File Systems: Removing directories/files while maintaining order.
• Autocomplete Systems: Removing entries in sorted tree structures.
• Game Trees: Updating decision trees dynamically.

Conclusion

The Delete Node in a BST problem is a fundamental exercise in BST traversal, recursion and tree restructuring.

By practicing this problem, you improve your understanding of:

• Handling multiple deletion cases in BSTs
• Recursion for hierarchical structures
• Maintaining BST properties after modifications

This problem is essential for technical interviews and practical applications involving hierarchical datasets.

Related Reads

• Number of Provinces – LeetCode75 Python Solution Explained
• Binary Tree Right Side View – LeetCode75 Python Solution Explained
• Leaf-Similar Trees – LeetCode75 Python Solution Explained
• Lowest Common Ancestor of a Binary Tree – LeetCode75 Python Solution Explained
• Longest ZigZag Path in a Binary Tree – LeetCode75 Python Solution Explained

References

1. LeetCode – Delete Node in a BST
2. GeeksforGeeks – Deletion in BST
3. Programiz – Binary Search Tree Operations
4. TutorialsPoint – BST Deletion