Understanding iterative deletion

Just like insertion, we can also delete a given value from a binary search tree iteratively. Since we only move from top to bottom in the tree and do not backtrack, we can replace the recursive function calls with loops to get an iterative algorithm.

Algorithm

The idea is simple. We know that deletion is a two-step process: in the first step, we search for the node to be deleted, and then in the second step, we delete it. We need to convert the first step to its iterative form to get an iterative algorithm. Once we find the node to be deleted, we remove the links to it from its parent.

To delete a node, we need access to its parent. Unlike in the recursive algorithm, we cannot rely on the recursive call stack to hold the parent's information, so we must keep track of it while traversing iteratively.

1. Node to be deleted is a leaf node

This is the most straightforward case of deletion. If the node to be deleted is the leaf node, we can search for it using the iterative search algorithm we learned earlier and delete it.