Deletion in BST

The delete function in a binary search tree removes a specified node, ensuring the binary search tree property is maintained. Three scenarios govern node deletion. This article explores the process of deleting nodes in a binary tree while introducing the fundamentals of what a binary search tree entails.

To learn more about the Binary search tree. click here

Deletion in Binary Search Tree

A binary search tree's given node can be removed using the delete function. However, we have to remove a node from a binary search tree in a way that doesn't break that property(A node's right subtree only contains nodes with keys higher than the node's key, and its left subtree only contains nodes with keys lower than the node's key. A binary search tree must also be present in both the left and right subtrees.). There are three instances of deleting a node from a binary search tree.

The Node to be Deleted in Binary Search Tree is a Leaf Node

This is the simplest scenario. Simply replace the leaf node with NULL/None and release the space that has been allotted.

In the Above BST if we want to delete 17 we will replace this with None/Null.

The Node to be Deleted in Binary Search Tree has Only One Child

Replace the node in this instance with its child and then remove the child node because it now has the value that needs to be destroyed. Simply replace it with NULL to release the space that was allotted.

In the above BST if we want to delete 8 then we replace it with 10 and remove 10 or copy 10to the 8 and remove 10.

The Node to be Deleted in Binary Search Tree has Two Children

Compared to the previous two situations, it is a little more complicated. However, until the node value (to be deleted) is placed on the leaf of the tree, the node that is to be removed is replaced by its in-order successor or predecessor recursively.

Inorder Successor :
The following node in the Binary Tree's Inorder traversal is referred to as a node's Inorder successor. For the final node in an inorder traverse, Inorder Successor is NULL.

In the above BST if we want to remove 5 then first we will find an inorder successor(To get a node which is just greater than the node to be deleted) so the inorder successor is 8 so we replace 5(node to be deleted) with 8(inorder successor) and delete 8.

Example

Problem Statement

Given a binary search tree and a key value. The task is to delete

Algorithm

Step - 1 :
if root is null then return null.
Step - 2 :
if root.key < key then find the node in right subtree root.right=delNode(root.right.key).
Step - 3 :
if root.key > key then find the node in left subtree root.right=delNode(root.right.key).
Step - 4 :
if root.key==key

• if root.left == null and root.right == null then return null
• if root.left==null return root.right
• if root.right=null return root.left
• if root.left!=null and root.right!=null then find inorder successor or predecessor and replace it with the root node and delete inorder successor or predecessor.

Code

Python :

Java :

CPP :

Complexity

Time Complexity :
$O(logN)$, N = the number of nodes. Due to the fact that the given tree is a BST, we need to traverse either the right subtree or the left subtree at any given point. Therefore, $log(N)$ is the time complexity.

Space Complexity :
For a recursion stack, the space complexity is $O(H)$, where H is the BST's height