I am trying to remove a node from a BST and I actually got the code to work but there is one part of it I do not understand. This is my code:
class BST {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
remove(value, parentNode = null) {
let currentNode = this;
while (currentNode !== null) {
if (value < currentNode.value) {
parentNode = currentNode;
currentNode = currentNode.left;
} else if (value > currentNode.value) {
parentNode = currentNode;
currentNode = currentNode.right;
} else {
if (currentNode.left !== null && currentNode.right !== null) {
currentNode.value = currentNode.right.getMinValue();
currentNode.right.remove(currentNode.value, currentNode);
} else if (parentNode === null) {
if (currentNode.left !== null) {
currentNode.value = currentNode.left.value;
currentNode.right = currentNode.left.right;
currentNode.left = currentNode.left.left;
} else if (currentNode.right !== null) {
currentNode.value = currentNode.right.value;
currentNode.left = currentNode.right.left;
currentNode.right = currentNode.right.right;
}
} else if (parentNode.left === currentNode) {
parentNode.left = currentNode.left !== null ? currentNode.left : currentNode.right;
} else if (parentNode.right === currentNode) {
parentNode.right = currentNode.left !== null ? currentNode.left : currentNode.right;
}
break;
}
}
return this;
}
getMinValue() {
let currentNode = this;
while (currentNode.left !== null) {
currentNode = currentNode.left;
}
return currentNode.value;
}
}
I use the getMinValue method for the edge case where I have to remove a node with two children nodes. I use that method to replace the current node’s value (the one that I’m removing) with the lowest value from the right subtree of that node. I then call the remove method to remove that same node from the right subtree.
What I don’t understand is the following line:
currentNode.right.remove(currentNode.value, currentNode);
I know that this line is removing the node that was used as a replacement for the base node but I don’t understand why I have to pass the currentNode as the parentNode argument.
Won’t the remove method have to find the node that needs to be removed first and hence change the parentNode value anyways? Why can’t I just make that argument null?
2
Answers
This algorithm keeps track of
parentNodeas it descends through the tree so that it can set theparentNode.leftorparentNode.rightproperty tonullwhenevercurrentNodeturns out to be the node to be removed.Now when you call
removeagain in the case you describe, you also need to pass on a reference forparentNode, as it might be that thiscurrentNode.rightis a node without left child, and thus is the one that needs to be removed. For that removal to happen, its parent node needs itsrightproperty to be set tonull, and so a reference to it is needed.If you would pass
nullfor that parameter it would work fine in cases wherecurrentNode.righthas a left child — you would descend further down and so setparentNodeappropriately. But for the case where it doesn’t have a left child, it is that node that needs to be removed, and so we need to know its parent.parentNodeis needed when the node being removed is the root of the subtree. In this case, the appropriate child link in the parent has to be updated to point to the corresponding child of the node being removed.When
parentNode === null, it means you’re removing the top-most node in the entire BST, so there’s no parent to update. You can’t use that code path when you’re removing a node in the middle of the tree.