From the course: Data Structures in JavaScript: Trees and Graphs

Unlock this course with a free trial

Join today to access over 25,500 courses taught by industry experts.

Binary search tree implementation: delete

Binary search tree implementation: delete

From the course: Data Structures in JavaScript: Trees and Graphs

Start my 1-month free trial Buy for my team

Binary search tree implementation: delete

“

- [Instructor] In this lesson, we'll implement the delete operation for a binary search tree. Let's walk through how deletion works step by step. The delete method takes three parameters, val, the value we want to remove, node which defaults to this.root and parent which defaults to null. We start with a while loop that continues as long as the node is not null Inside the loop, we compare the target value with the current nodes value to determine our direction. If the value is less than node.value, we move to the left child. If value is greater, we move to the right child. Now, if neither of these conditions are true, that means we found a node you want to delete. At this point, we handle three possible cases. Case one, if the node has two children. We need to preserve the BST structure when the node has both a left and right child. To do that, we have to find the in-order successor, the smallest value in the right subtree. We'll use a helper function called findMin for this. It…

Contents