no-stack-dub-sack
commented
6 years ago Hi @mansisce, disregard my last message if you saw it before I deleted it. I forgot I already had made changes to the BST solution a while back :-)
You are quite right, nice catch! Really, the better solution would just be node = node.right and node = node.left, respectively, but for some reason I can't figure out, this messes up trying to remove the root node of a tree with only two nodes, e.g.
if the solution is:
// node only has right child
else if (!node.left) {
node = node.right;
}
// node only has left child
else if (!node.right) {
node = node.left;
}and then you run tree.remove(15), the tree is unchanged, when really the root node should be 27. Which, frankly, does not make sense to me!
Anyway, to keep this working, I think you need to make the assignments that you have in bold in your comment in the opposite order, e.g.:
// node only has right child
else if (!node.left) {
node.value = node.right.value;
node.left = node.right.left; // above the node.right assignment
node.right = node.right.right;
}
// node only has left child
else if (!node.right) {
node.value = node.left.value;
node.right = node.left.right; // above the node.left assignment
node.left = node.left.left;
}Otherwise, an example like this wouldn't work if you tried to delete 17
because if the code was like this:
else if (!node.left) {
node.value = node.right.value;
node.right = node.right.right;
// now, node.right is null after the above line executes
node.left = node.right.left; // TypeError: Cannot read property 'left' of null
}the node.left = node.right.left assignment would fail. To protect against this, you need to assign the node on the side that we're not replacing first.
Do you want to go ahead and make this change? Thanks again for catching this pretty serious bug, if there was a lot of data in the other pointer, it would all get lost in a real world implementation!
mansisce
We are not handling the both left and right pointers when we delete the node. Update will be as mentioned below
// node only has right child else if (!node.left) { node.value = node.right.value node.right = node.right.right node.left = node.right.left; } // node only has left child else if (!node.right) { node.value = node.left.value node.left = node.left.left node.right = node.left.right }