# 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.

### 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.