nzakas/computer-science-in-javascript — Issue #6: Removing a node with two children messes up the structure
Author: alekop
Created: 2011-12-02 00:44:44+00:00
State: open

First off, thanks for sharing. This is a very clean, easy to follow implementation. Very nice.

The only issue I found is when deleting nodes with two children. Try this:
var bst = new BinarySearchTree();
bst.add(7);
bst.add(11);
bst.add(8);
bst.add(13);

At this point the structure looks like this:
7
\
11
/ \
8 13

bst.remove(11);

Expected result:
7
\
8
\
13

Actual result:
7
\
8
/
8

Node 8's left pointer points to itself, and the right node has been overwritten.

This line seems odd:

275: replacementParent.right = replacement.left;

This is where node 11 loses its 13 branch.

And

279: replacement.left = current.left;

assigns node 8 to itself.

Hope this helps. Thanks again.