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.