ProgramGuru

Delete a Node in a Binary Search Tree

Problem and examples

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.

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.

How it works

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.

  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.

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

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

TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return nullptr;
    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;
            delete root;
            return temp;
        } else if (!root->right) {
            TreeNode* temp = root->left;
            delete 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) {
        inorder(root->left);
        cout << root->val << " ";
        inorder(root->right);
    }
}

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

    root = deleteNode(root, 3);
    cout << "Inorder after deletion: ";
    inorder(root);
    cout << endl;
    return 0;
}

Python implementation

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 None
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        temp = findMin(root.right)
        root.val = temp.val
        root.right = deleteNode(root.right, temp.val)
    return root

def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []

if __name__ == '__main__':
    root = TreeNode(5,
                    TreeNode(3, TreeNode(2), TreeNode(4)),
                    TreeNode(7, TreeNode(6), TreeNode(8)))
    root = deleteNode(root, 3)
    print("Inorder after deletion:", inorder(root))

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class DeleteNodeInBST {
    public 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 == null) return root.right;
            if (root.right == null) return root.left;
            TreeNode min = findMin(root.right);
            root.val = min.val;
            root.right = deleteNode(root.right, min.val);
        }
        return root;
    }

    private TreeNode findMin(TreeNode node) {
        while (node.left != null)
            node = node.left;
        return node;
    }

    private void inorder(TreeNode root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.val + " ");
            inorder(root.right);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(8);

        DeleteNodeInBST obj = new DeleteNodeInBST();
        root = obj.deleteNode(root, 3);
        System.out.print("Inorder after deletion: ");
        obj.inorder(root);
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function findMin(node) {
    while (node.left) node = node.left;
    return node;
}

function deleteNode(root, key) {
    if (!root) 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) return root.right;
        if (!root.right) return root.left;
        let temp = findMin(root.right);
        root.val = temp.val;
        root.right = deleteNode(root.right, temp.val);
    }
    return root;
}

function inorder(root) {
    return root ? [...inorder(root.left), root.val, ...inorder(root.right)] : [];
}

const root = new TreeNode(5,
    new TreeNode(3, new TreeNode(2), new TreeNode(4)),
    new TreeNode(7, new TreeNode(6), new TreeNode(8)));

const updatedRoot = deleteNode(root, 3);
console.log("Inorder after deletion:", inorder(updatedRoot));

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

func findMin(node *TreeNode) *TreeNode {
    for node.left != nil {
        node = node.left
    }
    return node
}

func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }
    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 == nil {
            return root.right
        }
        if root.right == nil {
            return root.left
        }
        temp := findMin(root.right)
        root.val = temp.val
        root.right = deleteNode(root.right, temp.val)
    }
    return root
}

func inorder(root *TreeNode) {
    if root != nil {
        inorder(root.left)
        fmt.Print(root.val, " ")
        inorder(root.right)
    }
}

func main() {
    root := &TreeNode{5, nil, nil}
    root.left = &TreeNode{3, &TreeNode{2, nil, nil}, &TreeNode{4, nil, nil}}
    root.right = &TreeNode{7, &TreeNode{6, nil, nil}, &TreeNode{8, nil, nil}}

    root = deleteNode(root, 3)
    fmt.Print("Inorder after deletion: ")
    inorder(root)
    fmt.Println()
}

Rust implementation

use std::rc::Rc;
use std::cell::RefCell;

type Node = Option<Rc<RefCell<TreeNode>>>;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Node,
    right: Node,
}

fn find_min(mut node: Node) -> Node {
    while let Some(left) = node.as_ref().unwrap().borrow().left.clone() {
        node = Some(left);
    }
    node
}

fn delete_node(root: Node, key: i32) -> Node {
    match root {
        Some(node_rc) => {
            let mut node = node_rc.borrow_mut();
            if key < node.val {
                node.left = delete_node(node.left.clone(), key);
            } else if key > node.val {
                node.right = delete_node(node.right.clone(), key);
            } else {
                if node.left.is_none() {
                    return node.right.clone();
                }
                if node.right.is_none() {
                    return node.left.clone();
                }
                let min_node = find_min(node.right.clone());
                node.val = min_node.as_ref().unwrap().borrow().val;
                node.right = delete_node(node.right.clone(), node.val);
            }
            Some(Rc::clone(&node_rc))
        },
        None => None,
    }
}

Kotlin implementation

class TreeNode(var val: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun findMin(node: TreeNode): TreeNode {
    var curr = node
    while (curr.left != null) curr = curr.left!!
    return curr
}

fun deleteNode(root: TreeNode?, key: Int): TreeNode? {
    root ?: 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 == null) return root.right
        if (root.right == null) return root.left
        val minNode = findMin(root.right!!)
        root.val = minNode.val
        root.right = deleteNode(root.right, minNode.val)
    }
    return root
}

fun inorder(root: TreeNode?) {
    if (root != null) {
        inorder(root.left)
        print("${root.val} ")
        inorder(root.right)
    }
}

fun main() {
    val root = TreeNode(5)
    root.left = TreeNode(3).apply {
        left = TreeNode(2)
        right = TreeNode(4)
    }
    root.right = TreeNode(7).apply {
        left = TreeNode(6)
        right = TreeNode(8)
    }
    val updated = deleteNode(root, 3)
    print("Inorder after deletion: ")
    inorder(updated)
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

func findMin(_ node: TreeNode) -> TreeNode {
    var curr = node
    while let next = curr.left {
        curr = next
    }
    return curr
}

func deleteNode(_ root: TreeNode?, _ key: Int) -> TreeNode? {
    guard let root = root else { return nil }
    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 == nil { return root.right }
        if root.right == nil { return root.left }
        let minNode = findMin(root.right!)
        root.val = minNode.val
        root.right = deleteNode(root.right, minNode.val)
    }
    return root
}

func inorder(_ root: TreeNode?) {
    if let node = root {
        inorder(node.left)
        print("\(node.val)", terminator: " ")
        inorder(node.right)
    }
}

let root = TreeNode(5)
root.left = TreeNode(3)
root.left?.left = TreeNode(2)
root.left?.right = TreeNode(4)
root.right = TreeNode(7)
root.right?.left = TreeNode(6)
root.right?.right = TreeNode(8)

let updated = deleteNode(root, 3)
print("Inorder after deletion:", terminator: " ")
inorder(updated)

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function findMin(node: TreeNode): TreeNode {
    while (node.left !== null) {
        node = node.left;
    }
    return node;
}

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
    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) return root.right;
        if (!root.right) return root.left;
        let temp = findMin(root.right);
        root.val = temp.val;
        root.right = deleteNode(root.right, temp.val);
    }
    return root;
}

function inorder(root: TreeNode | null): number[] {
    return root ? [...inorder(root.left), root.val, ...inorder(root.right)] : [];
}

const root = new TreeNode(5,
    new TreeNode(3, new TreeNode(2), new TreeNode(4)),
    new TreeNode(7, new TreeNode(6), new TreeNode(8)));

const updated = deleteNode(root, 3);
console.log("Inorder after deletion:", inorder(updated));