Java: How to Delete a Node in Binary Search Tree

Shivani Dwivedi

Follow

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.

Github link to the solution: https://github.com/shivanidwivedi/JavaProgramming/commit/732d5ed122dfc90741e62d85e4e39de1c394052d