To delete an element from a BST, first locate it in the tree and then consider two cases—whether or not the node has a left child—before deleting the element and reconnecting the tree. The **insert(element)** method was presented in the post. Often you need to delete an element from a binary search tree. Doing so is far more complex than adding an element into a binary search tree.

To delete an element from a binary search tree, you need to first locate the node that contains the element and also its parent node. Let **current** point to the node that contains the element in the binary search tree and **parent** point to the parent of the **current** node. The **current** node may be a left child or a right child of the **parent** node. There are two cases to consider.

**Case 1**: The current node does not have a left child, as shown in Figure below (a). In this case, simply connect the parent with the right child of the current node, as shown in Figure below (b).

For example, to delete node **10** in Figure below (a), you would connect the parent of node **10** with the right child of node **10**, as shown in Figure below (b).

If the current node is a leaf, it falls into Case 1. For example, to delete element **16** in Figure above (a), connect its right child (in this case, it is **null**) to the parent of node **16**.

Case 2: The **current** node has a left child. Let **rightMost** point to the node that contains the largest element in the left subtree of the **current** node and **parentOfRightMost** point to the parent node of the **rightMost** node, as shown in Figure below (a). Note that the **rightMost** node cannot have a right child but may have a left child. Replace the element value in the **current** node with the one in the **rightMost** node, connect the **parentOfRightMost** node with the left child of the **rightMost** node, and delete the rightMost node, as shown in Figure below (b).

For example, consider deleting node **20** in Figure below (a). The **rightMost** node has the element value **16**. Replace the element value **20** with **16** in the **current** node and make node **10** the parent for node **14**, as shown in Figure below (b).

The algorithm for deleting an element from a binary search tree can be described in the code below.

`1 boolean delete(E e) {`

2 Locate element e in the tree;

3 if element e is not found

4 return true;

5

6 Let current be the node that contains e and parent be

7 the parent of current;

8

9 if (current has no left child) // Case 1

10 Connect the right child of

11 current with parent; now current is not referenced, so

12 it is eliminated;

13 else // Case 2

14 Locate the rightmost node in the left subtree of current.

15 Copy the element value in the rightmost node to current.

16 Connect the parent of the rightmost node to the left child

17 of rightmost node;

18

19 return true; // Element deleted

20 }

The complete implementation of the **delete** method is given in lines 153–211 in BST.java. The method locates the node (named **current**) to be deleted and also locates its parent (named **parent**) in lines 155–168. If **current** is **null**, the element is not in the tree. Therefore, the method returns **false** (line 171). Please note that if **current** is **root**, **parent** is **null**. If the tree is empty, both **current** and **parent** are **null**.

Case 1 of the algorithm is covered in lines 174–185. In this case, the **current** node has no left child (i.e., **current.left == null**). If **parent** is **null**, assign **current.right** to **root** (lines 176–178). Otherwise, assign **current.right** to either **parent.left** or **parent.right**, depending on whether **current** is a left or right child of **parent** (180–183).

Case 2 of the algorithm is covered in lines 186–207. In this case, **current** has a left child. The algorithm locates the rightmost node (named **rightMost**) in the left subtree of the current node and also its parent (named **parentOfRightMost**) (lines 193–196). Replace the element in **current** by the element in **rightMost** (line 199); assign **rightMost.left** to either **parentOfRightMost.right** or **parentOfRightMost.left** (lines 202–206), depending on whether **rightMost** is a right or left child of **parentOfRightMost**.

The code below gives a test program that deletes the elements from the binary search tree.

`Inorder (sorted): Adam Daniel George Jones Michael Peter Tom`

Postorder: Daniel Adam Jones Peter Tom Michael George

Preorder: George Adam Daniel Michael Jones Tom Peter

The number of nodes is 7

`After delete George:`

Inorder (sorted): Adam Daniel Jones Michael Peter Tom

Postorder: Adam Jones Peter Tom Michael Daniel

Preorder: Daniel Adam Michael Jones Tom Peter

The number of nodes is 6

`After delete Adam:`

Inorder (sorted): Daniel Jones Michael Peter Tom

Postorder: Jones Peter Tom Michael Daniel

Preorder: Daniel Michael Jones Tom Peter

The number of nodes is 5

`After delete Michael:`

Inorder (sorted): Daniel Jones Peter Tom

Postorder: Peter Tom Jones Daniel

Preorder: Daniel Jones Tom Peter

The number of nodes is 4

Figures below show how the tree evolves as the elements are deleted from it.

It is obvious that the time complexity for the inorder, preorder, and postorder is O(n), since each node is traversed only once. The time complexity for search, insertion, and deletion is the height of the tree. In the worst case, the height of the tree is O(n). If a tree is well-balanced, the height would be O(logn).

## Top comments (0)