Understanding iterative insertion of a leaf

As we learned earlier, the recursive traversal algorithm performs poorly for some binary tree structures because of the choice of moving only in one direction. There is another way to insert a leaf node that will perform better in those cases. We can use the iterative level order traversal to insert a leaf node.

Algorithm

The algorithm is still the same. We move in the tree using the level order traversal algorithm. This way, we only move to the next level once we have checked all the nodes for the current level.