Delete a Node in a Binary Search Tree - Algorithm and Code Examples

Problem Statement❯

Given a binary search tree (BST) and a value key, your task is to delete the node with the given key from the tree. If the node does not exist, return the original tree unchanged. The tree must remain a valid BST after the deletion.

A Binary Search Tree is a binary tree where each node has a value, and for any given node:

The left subtree contains only nodes with values less than the node’s value.
The right subtree contains only nodes with values greater than the node’s value.

You may assume that duplicate values do not exist in the BST.

Examples❯

Input Tree	Key to Delete	Output Tree	Description
[5, 3, 6, 2, 4, null, 7]	3	[5, 4, 6, 2, null, null, 7]	Node 3 is deleted and replaced by its in-order successor (4).
[50, 30, 70, 20, 40, 60, 80]	70	[50, 30, 80, 20, 40, 60]	Node 70 is deleted and replaced by its in-order successor (80), maintaining BST properties.
[10, 5, 15, null, null, 12, 20]	15	[10, 5, 20, null, null, 12]	Node 15 is replaced by its in-order successor 20, which retains the subtree rooted at 12.
[8, 3, 10, 1, 6, null, 14]	1	[8, 3, 10, null, 6, null, 14]	Leaf node 1 is simply removed with no structural changes.
[7, 3, 9, null, 5, 8, 10]	9	[7, 3, 10, null, 5, 8]	Node 9 is replaced with its in-order successor 10. The subtree rooted at 8 remains intact.

Solution❯

Understanding the Problem

We are given a Binary Search Tree (BST) and a key. Our goal is to delete the node with the given key from the BST while maintaining the properties of a BST:

All values in the left subtree are less than the node’s value.
All values in the right subtree are greater than the node’s value.

This problem helps us understand recursive tree operations and handling multiple cases based on the structure of the tree.

Step-by-Step Solution with Example

Step 1: Understand the Input Example

Consider the following BST:


       5
      /      3   6
    /        2   4    7

Let’s say we want to delete the node with value 3. Node 3 has two children: 2 and 4.

Step 2: Traverse the Tree to Locate the Node

We start from the root (5). Since 3 is less than 5, we go to the left child. Now we are at 3, which matches the key. So this is the node we want to delete.

Step 3: Handle the Case - Node Has Two Children

Node 3 has both left and right children. In such cases, we:

Find the in-order successor (smallest value in the right subtree). Here, that’s 4.
Replace the value of node 3 with 4.
Now we recursively delete the node with value 4 in the right subtree.

This keeps the BST structure valid.

Step 4: Recursively Delete the In-Order Successor

Now we move to the right subtree of node 3 (which now has value 4). We find node 4, which is a leaf (no children), so we delete it by returning null.

Step 5: Final Tree After Deletion

The updated BST looks like this:


       5
      /      4   6
    /         2        7

Node 3 has been replaced by 4, and the original 4 node is removed.

Edge Cases

Edge Case 1: Deleting from an Empty Tree

If the root is null, the tree is empty. There's nothing to delete, so we return null.

Edge Case 2: Node Not Found

If we reach a null node during traversal and haven’t found the key, it means the key doesn’t exist. We simply return the current node.

Edge Case 3: Node is a Leaf

If the node to delete has no children, we can directly remove it by returning null.

Edge Case 4: Node with One Child

If the node has only one child, we return that child and skip the current node, effectively deleting it.

Finally

Deleting a node from a BST involves careful consideration of three scenarios: deleting a leaf, deleting a node with one child, and deleting a node with two children. Using recursion helps elegantly handle each case. Understanding in-order successor and BST structure rules is key to solving this problem correctly and efficiently.

Algorithm Steps❯

Given a binary search tree (BST) and a key to delete.
If the BST is empty, return null or the empty tree.
If key is less than the value at the current node, recursively delete the node in the left subtree.
If key is greater than the value at the current node, recursively delete the node in the right subtree.
If key equals the current node's value, then this is the node to be deleted:

If the node is a leaf, remove it.
If the node has one child, replace it with its child.
If the node has two children, find the minimum node in its right subtree (successor), copy its value to the current node, and then recursively delete the successor from the right subtree.

Return the (possibly new) root of the BST.

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findMin(node):
    while node.left:
        node = node.left
    return node


def deleteNode(root, key):
    if not root:
        return root
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        # Node with only one child or no child
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        # Node with two children: Get the inorder successor
        temp = findMin(root.right)
        root.val = temp.val
        root.right = deleteNode(root.right, temp.val)
    return root

# Example usage:
if __name__ == '__main__':
    # Build a BST and delete a node with key
    root = TreeNode(5,
            TreeNode(3, TreeNode(2), TreeNode(4)),
            TreeNode(7, TreeNode(6), TreeNode(8)))
    root = deleteNode(root, 3)
    # Function to print inorder traversal for verification
    def inorder(root):
        return inorder(root.left) + [root.val] + inorder(root.right) if root else []
    print('Inorder after deletion:', inorder(root))

⬅ Previous TopicFind a Value in a Binary Search Tree

Next Topic ⮕Find the Minimum Value in a Binary Search Tree

Comments

Loading comments...