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

Contents

ProblemExamplesSolutionAlgorithmCode

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❯

1. Deleting from an Empty Tree

If the binary search tree is empty (i.e., the root is null), there's nothing to delete. We simply return the tree as is — which is still empty. This is a base case and helps terminate recursion safely.

2. Deleting a Leaf Node (Node with No Children)

Suppose the node to be deleted is a leaf, meaning it has no left or right children. In this case, we can safely remove the node by setting its parent's pointer to null. For example, deleting 3 from a tree where 3 has no children results in simply detaching it from its parent.

3. Deleting a Node with One Child

If the node to be deleted has only one child, the simplest approach is to bypass the node and connect its parent directly to its only child. This ensures the BST structure remains intact. For instance, deleting a node like 7 that only has a right child (8) would mean linking 7’s parent directly to 8.

4. Deleting a Node with Two Children

This is the most complex case. If a node has both left and right children, we must maintain the BST properties. The standard solution is to replace the value of the node with its in-order successor (the smallest value in the right subtree), and then recursively delete the successor node. This ensures that all left values remain smaller and right values remain larger, preserving the BST structure.

5. Key Not Found in the Tree

During traversal, if we reach a null node and haven't found the key, it means the key does not exist in the tree. In this case, the original tree remains unchanged. We simply return the node back up the recursive stack.

In all cases, it's important to preserve the structure and rules of a binary search tree while performing the deletion operation.

Algorithm Steps❯

  1. Given a binary search tree (BST) and a key to delete.
  2. If the BST is empty, return null or the empty tree.
  3. If key is less than the value at the current node, recursively delete the node in the left subtree.
  4. If key is greater than the value at the current node, recursively delete the node in the right subtree.
  5. If key equals the current node's value, then this is the node to be deleted:
    1. If the node is a leaf, remove it.
    2. If the node has one child, replace it with its child.
    3. 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.
  6. Return the (possibly new) root of the BST.

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
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))