Understanding iterative insertion

We can insert a given value in a binary search tree iteratively, like the search algorithm. 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 insertion is a two-step process. In the first step, we search for the insertion position and then insert the node in the second step. We need to convert the first step to its iterative form to get an iterative algorithm. Once we find the insertion position, we create a new node and return its reference to the caller.