Deletion in Binary Search Tree
(Reading time: 5 minutes)
The function to remove a node from a binary search tree is as follows:
remove(data) {this.root = this.removeNode(this.root, data)}removeNode(node, data) {if (!node) {return null;}if (data < node.data) {node.left = this.removeNode(node.left, data);return node;} else if (data > node.data) {node.right = this.removeNode(node.right, data);return node;} else {if (!node.left && !node.right) {node = null;return node;}if (!node.left) {node = node.right;return node;}if (!node.right) {node = node.left;return node;}let min = this.findMinNode(node.right);node.data = min.data;node.right = this.removeNode(node.right, min.data);return node;}}
Removing a leaf
First, we invoke the remove function. We set the root’s value equal to whatever gets returned from the removeNode function. We pass two arguments to this function: the root, and the node’s value that we want to delete, 9 in this case.
Inside the removeNode function, we get to the first if-statement. Nodes are present in the tree, so !node returns false. We get to the second if-statement, which returns true as data (9) is smaller than node.data (27). Now, we set the left node’s value equal to whatever gets returned from the removeNode function, which we invoke again, only now with the value of the left node (10) as the first argument.
Again, we get to the first if-statement, which returns false. The second if-statement returns true again, as data (9) is smaller than node.data ...