Delete a Node in Binary Search Tree

Problem Statement: Given a root node reference of a Binary Search Tree and a key, delete the node with the given key in the Binary Search Tree. Return the modified Binary Search Tree.

Examples

Example 1:

Input Format

Binary Search Tree: 5 3 6 2 4 -1 7

Key to Delete = 3

Output

Modified Binary Search Tree: 5 4 6 2 -1 -1 7

Or 

Modified Binary Search Tree: 5 2 6 -1 4 -1 7

Explanation

After removing the node with the key 3 from the binary search tree, the tree should be adjusted accordingly. In the place of 3, any of its child 2 or 4 can take place while preserving the binary search tree’s property that nodes to the left hold lesser values while those to the right hold greater values.


We only need to output any one of the valid answers.

Example 2:

Input Format: 

Binary Search Tree: 8 5 12 5 7 10 13 1 3 6 8 -1 -1 -1 -1 -1 -1 -1 4

Key to be Deleted: 5

Output: 

Modified Binary Search Tree: 8 2 12 1 3 10 13 -1 -1 -1 4 -1 -1 -1 -1 -1 7 6 8

Or

Modified Binary Search Tree: 8 7 12 6 8 10 13 2 -1 -1 -1 -1 -1 -1 -1 1 3 -1 -1 -1 4

Explanation

After removing the node with the key 5 from the binary search tree, the tree should be adjusted accordingly. In the place of 5, any of its child 2 or 7 can take place while preserving the binary search tree’s property that nodes to the left hold lesser values while those to the right hold greater values.

We only need to output any one of the valid answers.

Practice:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution:

Approach: 

To delete a node in a Binary Search Tree, start from the root and navigate to the node to delete based on its key. If the node is found, handle deletion based on three cases: if the node has no children, remove it; if it has one child, replace it with its child; if it has two children, find its inorder predecessor (the largest node in the left subtree), attach its right child to its parent, and connect the left child of the node to its parent’s new child. Return the modified BST after deletion.

Algorithm:

Step 1: Search for the node to delete:

Start from the root and if the key is less than the current node, move to the left subtree and if the key is greater than the current node, move to the right subtree. Repeat this until we find the node to delete or reach a null node.

Step 2: Handle Different Cases for Deletion:

Case 1: If the node has no children (leaf nodes), simply remove the node.
Case 2: If the node has one child, replace the node to be deleted with its child.
Case 3: If the node has two children,

  1. Find the node’s inorder predecessor by traversing the left subtree of the node to find the rightmost (largest) node. Store this as lastRight.
  2. Set the right child lastRight’s to the node to be deleted.
  3. Skip over the node to be deleted by directly connecting the root to the node’s left child ie. the root of the left subtree.

Step 3: Return the modified Binary Search Tree.

Code:

C++ Code

#include <iostream>
using namespace std;

// Definition of TreeNode structure
// for a binary tree node
struct TreeNode {
    // Value of the node
    int val;    
    
    // Pointer to the left child node
    TreeNode* left; 
    // Pointer to the right child node
    TreeNode* right;

    // Constructor to initialize the node with a
    // value and set left and right pointers to null
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};


class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        // Check if the root is empty
        if (root == NULL) {
            // Return null if the root is empty
            return NULL; 
        }
        
        // If the current root node has the key to be deleted
        if (root->val == key) {
            // Delete the node using the helper function
            return helper(root); 
        }
        
        // Create a dummy node pointing to the root
        TreeNode* dummy = root;
        // While loop to traverse the tree
        while (root != NULL) {
            // If the value to be deleted
            // is in the left subtree
            if (root->val > key) {
                // If the left child exists and
                // its value matches the key
                if (root->left != NULL && root->left->val == key) {
                   
                    // Delete the node using the helper function
                    root->left = helper(root->left); 
                    break;
                    
                } else {
                    // If the value is not in the left
                    // subtree, move to the right subtree
                    if (root->right != NULL && root->right->val == key) {
                         // Delete the node using the helper function
                        root->right = helper(root->right);
                        break;
                    } else {
                        // Move to the right subtree
                        root = root->right; 
                    }
                }
            }
        }
        
        // Return the modified tree
        return dummy; 
    }

    // Helper function to delete the node
    TreeNode* helper(TreeNode* root) {
        // If the left child of the root is null,
        // return the right child
        if (root->left == NULL) {
            return root->right;
            
        } else if (root->right == NULL) { 
            
            // If the right child is null,
            // return the left child
            return root->left;
        }
        
        // If both left and right children exist
        // Store the right child
        
        TreeNode* rightChild = root->right; 
        
        // Find the last right child of the left subtree
        TreeNode* lastRight = findLastRight(root->left);
        
        // Set the right child of the last
        // right node to the stored right child
        lastRight->right = rightChild; 
        
        // Return the left child as the new subtree
        return root->left; 
    }

    // Helper function to find the
    // last right node in a subtree
    TreeNode* findLastRight(TreeNode* root) {
        // Traverse to the rightmost node in the subtree
        if (root->right == NULL) {
            // Return the rightmost node
            return root; 
        }
        
        // Recursively find the last right node
        return findLastRight(root->right); 
    }
};


// Function to perform an in-order traversal
// of a binary tree and print its nodes
void printInOrder(TreeNode* root) {
    // Check if the current node
    // is null (base case for recursion)
    if (root == NULL) {
        // If null, return and
        // terminate the function
        return; 
    }

    // Recursively call printInOrder
    // for the left subtree
    printInOrder(root->left);
    
    // Print the value of the current node
    cout << root->val << " ";

    // Recursively call printInOrder
    // for the right subtree
    printInOrder(root->right);
}


int main() {
    Solution solution;

    // Creating a sample tree for testing purposes
    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);

    // Printing the original tree
    cout << "Original Tree (Inorder Traversal): ";
    printInOrder(root);
    cout << endl;

    // Testing the deleteNode function
    int keyToDelete = 3;
    TreeNode* updatedTree = solution.deleteNode(root, keyToDelete);
    // Printing the tree after deletion
    cout << "Tree After Deletion (Inorder Traversal): ";
    printInOrder(updatedTree);
    cout << endl;

    return 0;
}

Output:

Original Tree (Inorder Traversal): 2 3 4 5 6 7 8 

Tree After Deletion (Inorder Traversal): 2 4 5 6 7 8

Time Complexity: O(H) where H is the height of the tree. This is due to the binary search applied while finding the node with value as key. All other operations performed are in constant time. O(H) ~ O(log N) in case of a full binary search tree (optimal time).

Space Complexity: O(1) as no additional data structures or memory allocation is done

Java Code

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    // Constructor to initialize the node with a value and set left and right pointers to null
    TreeNode(int x) {
        val = x;
        left = null;
        right = null;
    }
}

class Solution {
    // Function to delete a node in a BST
    public TreeNode deleteNode(TreeNode root, int key) {
        // Check if the root is empty
        if (root == null) {
            // Return null if the root is empty
            return null;
        }

        // If the current root node has the key to be deleted
        if (root.val == key) {
            // Delete the node using the helper function
            return helper(root);
        }

        // Create a dummy node pointing to the root
        TreeNode dummy = root;

        // While loop to traverse the tree
        while (root != null) {
            // If the value to be deleted is in the left subtree
            if (root.val > key) {
                // If the left child exists and its value matches the key
                if (root.left != null && root.left.val == key) {
                    // Delete the node using the helper function
                    root.left = helper(root.left);
                    break;
                } else {
                    // If the value is not in the left subtree, move to the right subtree
                    if (root.right != null && root.right.val == key) {
                        // Delete the node using the helper function
                        root.right = helper(root.right);
                        break;
                    } else {
                        // Move to the right subtree
                        root = root.right;
                    }
                }
            }
        }
        // Return the modified tree
        return dummy;
    }

    // Helper function to delete the node
    public TreeNode helper(TreeNode root) {
        // If the left child of the root is null, return the right child
        if (root.left == null) {
            return root.right;
        } else if (root.right == null) {
            // If the right child is null, return the left child
            return root.left;
        }

        // If both left and right children exist
        TreeNode rightChild = root.right; // Store the right child
        TreeNode lastRight = findLastRight(root.left); // Find the last right child of the left subtree
        lastRight.right = rightChild; // Set the right child of the last right node to the stored right child
        return root.left; // Return the left child as the new subtree
    }

    // Helper function to find the last right node in a subtree
    public TreeNode findLastRight(TreeNode root) {
        // Traverse to the rightmost node in the subtree
        if (root.right == null) {
            return root; // Return the rightmost node
        }
        return findLastRight(root.right); // Recursively find the last right node
    }
}

public class Main {
    // Function to perform an in-order traversal of a binary tree and print its nodes
    public static void printInOrder(TreeNode root) {
        // Check if the current node is null (base case for recursion)
        if (root == null) {
            // If null, return and terminate the function
            return;
        }

        // Recursively call printInOrder for the left subtree
        printInOrder(root.left);

        // Print the value of the current node
        System.out.print(root.val + " ");

        // Recursively call printInOrder for the right subtree
        printInOrder(root.right);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        // Creating a sample tree for testing purposes
        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);

        // Printing the original tree
        System.out.print("Original Tree (Inorder Traversal): ");
        printInOrder(root);
        System.out.println();

        // Testing the deleteNode function
        int keyToDelete = 3;
        TreeNode updatedTree = solution.deleteNode(root, keyToDelete);
        
        // Printing the tree after deletion
        System.out.print("Tree After Deletion (Inorder Traversal): ");
        printInOrder(updatedTree);
        System.out.println();
    }
}

Output:

Original Tree (Inorder Traversal): 2 3 4 5 6 7 8 

Tree After Deletion (Inorder Traversal): 2 4 5 6 7 8

Time Complexity: O(H) where H is the height of the tree. This is due to the binary search applied while finding the node with value as key. All other operations performed are in constant time. O(H) ~ O(log N) in case of a full binary search tree (optimal time).

Space Complexity: O(1) as no additional data structures or memory allocation is done

Python Code

class TreeNode:
    """
    Definition of TreeNode structure
    for a binary tree node
    """
    def __init__(self, x):
        """
        Constructor to initialize the node with
        a value and set left and right pointers to null
        """
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def deleteNode(self, root, key):
        """
        Function to delete a node with a specified
        key from the binary search tree
        """
        if root is None:
            # Return None if the root is empty
            return None

        if root.val == key:
            # Delete the node using the helper function
            return self.helper(root)

        dummy = root
        while root is not None:
            if root.val > key:
                if root.left is not None and root.left.val == key:
                    # Delete the node using the helper function
                    root.left = self.helper(root.left)
                    break
                else:
                    if root.right is not None and root.right.val == key:
                        # Delete the node using the helper function
                        root.right = self.helper(root.right)
                        break
                    else:
                        root = root.right

        return dummy

    def helper(self, root):
        """
        Helper function to delete the node
        """
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left

        right_child = root.right
        last_right = self.find_last_right(root.left)
        last_right.right = right_child
        return root.left

    def find_last_right(self, root):
        """
        Helper function to find the last right node in a subtree
        """
        if root.right is None:
            return root
        return self.find_last_right(root.right)


def print_in_order(root):
    """
    Function to perform an in-order traversal
    of a binary tree and print its nodes
    """
    if root is None:
        return

    print_in_order(root.left)
    print(root.val, end=" ")
    print_in_order(root.right)


if __name__ == "__main__":
    solution = Solution()

    # Creating a sample tree for testing purposes
    root = TreeNode(5)
    root.left = TreeNode(3)
    root.right = TreeNode(7)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(4)
    root.right.left = TreeNode(6)
    root.right.right = TreeNode(8)

    # Printing the original tree
    print("Original Tree (Inorder Traversal): ", end="")
    print_in_order(root)
    print()

    # Testing the deleteNode function
    key_to_delete = 3
    updated_tree = solution.deleteNode(root, key_to_delete)
    # Printing the tree after deletion
    print("Tree After Deletion (Inorder Traversal): ", end="")
    print_in_order(updated_tree)
    print()

Output:

Original Tree (Inorder Traversal): 2 3 4 5 6 7 8 

Tree After Deletion (Inorder Traversal): 2 4 5 6 7 8

Time Complexity: O(H) where H is the height of the tree. This is due to the binary search applied while finding the node with value as key. All other operations performed are in constant time. O(H) ~ O(log N) in case of a full binary search tree (optimal time).

Space Complexity: O(1) as no additional data structures or memory allocation is done

JavaScript Code

// Definition of TreeNode structure
// for a binary tree node
class TreeNode {
    // Value of the node
    constructor(val) {
        this.val = val;
        // Pointer to the left child node
        this.left = null;
        // Pointer to the right child node
        this.right = null;
    }
}

class Solution {
    deleteNode(root, key) {
        // Check if the root is empty
        if (root === null) {
            // Return null if the root is empty
            return null;
        }

        // If the current root node has
        // the key to be deleted
        if (root.val === key) {
            // Delete the node using
            // the helper function
            return this.helper(root);
        }

        // Create a dummy node pointing to the root
        let dummy = root;
        // While loop to traverse the tree
        while (root !== null) {
            // If the value to be deleted
            // is in the left subtree
            if (root.val > key) {
                // If the left child exists and
                // its value matches the key
                if (root.left !== null && root.left.val === key) {

                    // Delete the node using the helper function
                    root.left = this.helper(root.left);
                    break;

                } else {
                    // If the value is not in the left
                    // subtree, move to the right subtree
                    if (root.right !== null && root.right.val === key) {
                        // Delete the node using the helper function
                        root.right = this.helper(root.right);
                        break;
                    } else {
                        // Move to the right subtree
                        root = root.right;
                    }
                }
            }
        }

        // Return the modified tree
        return dummy;
    }

    // Helper function to delete the node
    helper(root) {
        // If the left child of the root is null,
        // return the right child
        if (root.left === null) {
            return root.right;
        } else if (root.right === null) {

            // If the right child is null,
            // return the left child
            return root.left;
        }

        // If both left and right children exist
        // Store the right child
        let rightChild = root.right;

        // Find the last right child of the left subtree
        let lastRight = this.findLastRight(root.left);

        // Set the right child of the last
        // right node to the stored right child
        lastRight.right = rightChild;

        // Return the left child as the new subtree
        return root.left;
    }

    // Helper function to find the
    // last right node in a subtree
    findLastRight(root) {
        // Traverse to the rightmost node in the subtree
        if (root.right === null) {
            // Return the rightmost node
            return root;
        }

        // Recursively find the last right node
        return this.findLastRight(root.right);
    }
}

// Function to perform an in-order traversal
// of a binary tree and print its nodes
function printInOrder(root) {
    // Check if the current node
    // is null (base case for recursion)
    if (root === null) {
        // If null, return and
        // terminate the function
        return;
    }

    // Recursively call printInOrder
    // for the left subtree
    printInOrder(root.left);

    // Print the value of the current node
    console.log(root.val + " ");

    // Recursively call printInOrder
    // for the right subtree
    printInOrder(root.right);
}

// Creating a sample tree for testing purposes
let 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);

// Printing the original tree
console.log("Original Tree (Inorder Traversal): ");
printInOrder(root);
console.log("");

// Testing the deleteNode function
let solution = new Solution();
let keyToDelete = 3;
let updatedTree = solution.deleteNode(root, keyToDelete);

// Printing the tree after deletion
console.log("Tree After Deletion (Inorder Traversal): ");
printInOrder(updatedTree);
console.log("");

Output:

Original Tree (Inorder Traversal): 2 3 4 5 6 7 8 

Tree After Deletion (Inorder Traversal): 2 4 5 6 7 8

Time Complexity: O(H) where H is the height of the tree. This is due to the binary search applied while finding the node with value as key. All other operations performed are in constant time. O(H) ~ O(log N) in case of a full binary search tree (optimal time).

Space Complexity: O(1) as no additional data structures or memory allocation is done

In case you are learning DSA, you should definitely check out our free A2Z DSA Course with videos and blogs.

Special thanks to Gauri Tomar for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article