# Deletion from BST (Binary Search Tree)

Given a BST, write an efficient function to delete a given key in it.

To delete a node from BST, there are three possible cases to consider:

Case 1: Deleting a node with no children: simply remove the node from the tree.

Case 2: Deleting a node with two children: call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-order predecessor node, R. Copy the value of R to N, then recursively call delete on R until reaching one of the first two cases. If you choose in-order successor of a node, as right sub tree is not NULL (Our present case is node has 2 children), then its in-order successor is node with least value in its right sub tree, which will have at a maximum of 1 sub tree, so deleting it would fall in one of the first 2 cases.

Case 3: Deleting a node with one child: remove the node and replace it with its child.

Broadly speaking, nodes with children are harder to delete. As with all binary trees, a node’s in-order successor is its right subtree’s left-most child, and a node’s in-order predecessor is the left subtree’s right-most child. In either case, this node will have zero or one children. Delete it according to one of the two simpler cases above.

## Java

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1)

Above solution initially search the key in the BST and also find its parent pointer. We can easily modify the code to recursively search the key in deletion procedure itself and let recursion take care of updating the parent pointer.

## Java

The time complexity of above solution is O(n).

Searching in BST

(3 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest

Awesome

Guest
krishna kumar

In Case 2 picture, after deleting the 20 node and put across the 16 node in place of 20 node, it made tree not BST, i believe 20 node must be replace with 19 so that left node would always be less than the immediate parent node and right node would always fall in greater with immediate parent.

Guest

Good work!

Guest

It was really helpful thanks a lot

Guest
Abhinay Jain

very well explained.

Guest
Ankit Sharma

There is a mistake in the Java version of the code

Line 68 and 73 we’re not storing the addresses
root.left = deleteNode(root.left, data)
root.right = deleteNode(root.right, data)

Guest

can any one give me a code in c programming