# Java: How to Delete a Node in Binary Search Tree

Jul 23, 2020 · 2 min read

Problem Statement: Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference of the BST.

BST is a tree in which every node in the left subtree have value lesser than the root node and nodes in the right subtree have value greater than the root node.

To delete a node in a BST:

1. Find the node to be deleted.
2. Remove it and replace it with its successor/predecessor and update the BST.

Example:

Code:

Explanation:

Recursive Approach:

Three cases:

1. Key is in the left subtree
2. Key is in the right subtree
3. Key is the root

We need to recursively call the node’s children in order to find the key. Once we find that the root is the key, identify the case:

1. Root is the leaf (no child): delete it
2. Root has one child: Replace the root with the child.
3. Root has both children: Replace it with successor/predecessor and delete it using recursion.

Complexity Analysis:

Time complexity: O(H) where H is the height of the tree(equivalent to O(log N)), N = total number of nodes.

Space complexity: O(H) to keep the recursion stack.

### By The Startup

Get smarter at building your thing. Subscribe to receive The Startup's top 10 most read stories — delivered straight into your inbox, once a week. Take a look.

Medium sent you an email at to complete your subscription.

Written by

## Shivani Dwivedi

Software Engineer

## The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +787K followers.

Written by

## Shivani Dwivedi

Software Engineer

## The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +787K followers.

## The Social Cost of Scaling Software — and Living With It.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app