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.

Deletion from BST case-1

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.

Deletion from BST

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

Deletion from BST case-3

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.


Download   Run Code


Download   Run Code

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.


Download   Run Complete Code


Download   Run Code

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

Insertion in BST

Searching in BST


1 Star2 Stars3 Stars4 Stars5 Stars (3 votes, average: 5.00 out of 5)


Thanks for reading.

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 🙂

Leave a Reply

newest oldest most voted
Notify of


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.


Good work!


It was really helpful thanks a lot

Abhinay Jain

very well explained.

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)


can any one give me a code in c programming