The methods we will create in this chapter are a little bit more complex than the ones we implemented in previous chapters. We will use a lot of recursion in our methods. If you are not familiar with recursion, please refer to Chapter 9, Recursion.
The following code is the first piece of the algorithm used to insert a new key in a tree:
insert(key) {
if (this.root == null) { // {1}
this.root = new Node(key); // {2}
} else {
this.insertNode(this.root, key); // {3}
}
}
To insert a new node (or key) into a tree, there are two steps that we need to follow.
The first step is verifying whether the insertion is a special case. The special case for the BST is if the node we are trying to add is the first one in the tree ...
