Algorithm

Starting from the root, we compare the key. If the key is smaller than the root’s key, we search in the left subtree. Similarly, we search in the right subtree if the key is greater than the root’s key.

Time Complexity: In the worst case, the key could be the deepest node. So, the insertion time complexity is $O(height)$ or $O(N)$.

---

Visualization