Delete a Node in a Binary Search Tree - Visualization

Binary Search Trees

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❯

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❯

  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

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left, *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

TreeNode* findMin(TreeNode* node) {
    while (node->left != NULL)
        node = node->left;
    return node;
}

TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == NULL) return NULL;
    if (key < root->val)
        root->left = deleteNode(root->left, key);
    else if (key > root->val)
        root->right = deleteNode(root->right, key);
    else {
        if (!root->left) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (!root->right) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        TreeNode* temp = findMin(root->right);
        root->val = temp->val;
        root->right = deleteNode(root->right, temp->val);
    }
    return root;
}

void inorder(TreeNode* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->val);
        inorder(root->right);
    }
}

int main() {
    TreeNode* root = createNode(5);
    root->left = createNode(3);
    root->right = createNode(7);
    root->left->left = createNode(2);
    root->left->right = createNode(4);
    root->right->left = createNode(6);
    root->right->right = createNode(8);

    root = deleteNode(root, 3);
    printf("Inorder after deletion: ");
    inorder(root);
    printf("\n");
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...