Java: How to Delete a Node in Binary Search Tree

Shivani Dwivedi
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.

Sign up for Top 10 Stories

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.

By signing up, you will create a Medium account if you don’t already have one. Review our Privacy Policy for more information about our privacy practices.

Check your inbox
Medium sent you an email at to complete your subscription.

Shivani Dwivedi

Written by

Software Engineer

The Startup

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

Shivani Dwivedi

Written by

Software Engineer

The Startup

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

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

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store