Learning JavaScript Data Structures and Algorithms - Third Edition

Removing a node

The next and last method we will create for our BST is the remove method. This is the most complex method we will create in this book. Let’s start with the method that will be available to be called from a tree instance, as follows:

remove(key) {
  this.root = this.removeNode(this.root, key); // {1}
}

This method receives the desired key to be removed, and it also calls removeNode, passing the root and key to be removed as parameters ({1}). One very important detail to note is that the root receives the return of the removeNode method. We will understand why in a second.

The complexity of the removeNode method is due to the different scenarios that we need to handle and also because it is recursive.

Let’s take a look at the ...