Insertion

In this lesson, we'll see how to insert a new key in a BST.

We'll cover the following

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)O(height) or O(N)O(N).

Visualization

Get hands-on with 1200+ tech skills courses.