Algorithm

A new key is always inserted as a leaf. We search for the location for a new key as mentioned in the previous lesson and insert the new node when we reach the end.

Time Complexity: In the worst case, we traverse to the deepest node. So insertion time complexity is $O(height)$ or $O(N)$.

Visualization