Java: How to Delete a Node in Binary Search Tree

Shivani Dwivedi
Jul 23 · 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.


The Startup

Medium's largest active publication, followed by +705K people. Follow to join our community.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch

Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore

Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

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