wmock wmock - 9 days ago 4
Javascript Question

Binary Search Tree JavaScript implementation - remove function

Here's my implementation for a Binary Search Tree in JavaScript. All functions appear to be working properly except for the

remove
function. Specifically, it seems to be removing nodes properly until there's 2 nodes left in the tree:

var binaryTreeNode = function (value) {
return {
value : value,
left : null,
right : null
};
};

var binarySearchTree = function () {
var tree = Object.create( binarySearchTreeMethods );
tree.root = null;
return tree;
};

var binarySearchTreeMethods = {

insert: function (value, node) {
var newNode = binaryTreeNode( value );

// check if tree is empty
if ( this.isEmpty() ) {
this.root = newNode;
return;
}

// initialize node
if ( node === void 0 ) node = this.root;

// compare value with node.value
if ( value <= node.value ) {
// check if left exists
if ( node.left ) {
this.insert( value, node.left );
} else {
node.left = newNode;
}
} else {
if ( node.right ) {
this.insert( value, node.right );
} else {
node.right = newNode;
}
}
},

remove: function (value, node) {
var nextRightValue, nextLeftValue, minRight;

if ( !this.isEmpty() ) {
// initialize node
if ( node === void 0 ) node = this.root;

// compare the node's value with the value
if ( value < node.value ) {
// check if there is a left node
if ( node.left ) {
node.left = this.remove( value, node.left );
}
} else if ( value > node.value ) {
// check if there is a right node
if ( node.right ) {
node.right = this.remove( value, node.right );
}
} else {
// at this point, value === node.value
// check if node is a leaf node
if ( node.left === null && node.right === null ) {
// edge case of single node in tree (i.e. root node)
if ( this.getHeight() === 0 ) {
this.root = null;
return this.root;
} else {
node = null;
}
} else if ( node.left === null ) {
node = node.right;
} else if ( node.right === null ) {
node = node.left;
} else {
// node has both left and right
minRight = this.findMinValue( node.right );
node.value = minRight;
node.right = this.remove( minRight, node.right );
}
}
return node;
}
},

contains: function (value, node) {
if ( this.isEmpty() ) return false;
// tree is not empty - initialize node
if ( node === void 0 ) node = this.root;

// check if node's value is the value
if ( value === node.value ) return true;
if ( value < node.value ) {
// check if left node exists
return node.left ? this.contains( value, node.left ) : false;
} else {
// check if right node exists
return node.right ? this.contains( value, node.right ) : false;
}
},

findMaxValue: function (node) {
if ( !this.isEmpty() ) {
if ( node === void 0 ) node = this.root;
while ( node.right ) {
node = node.right;
}
return node.value;
}
},

findMinValue: function (node) {
if ( !this.isEmpty() ) {
if ( node === void 0 ) node = this.root;
while ( node.left ) {
node = node.left;
}
return node.value;
}
},

getHeight: function (node) {
if ( !this.isEmpty() ) {
// initialize node
if ( node === void 0 ) node = this.root;

// base case
if ( node.left === null && node.right === null ) return 0;
if ( node.left === null ) return 1 + this.getHeight( node.right );
if ( node.right === null ) return 1 + this.getHeight( node.left );
return 1 + Math.max( this.getHeight( node.left ), this.getHeight( node.right ) );
}
},

isEmpty: function () {
return this.root === null;
}

};


Inserting values into the binary search tree works fine:

var bst = binarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(20);
bst.insert(30);
bst.insert(22);
bst.insert(18);


I come across an issue when I start removing the
root
value each time:


bst.remove(10); // this works fine and the resulting bst tree is structurally correct
bst.remove(18); // this works fine and the resulting bst tree is structurally correct
bst.remove(20); // this works fine and the resulting bst tree is structurally correct
bst.remove(22); // this works fine and the resulting bst tree is structurally correct
bst.remove(30); // THIS IS WHERE THE ISSUE OCCURS


Prior to removing 30, the tree only has two values: 30 as the root value and 5 as the root.left value. I would expect that removing 30 would give me a tree which has 5 as the root. However, removing 30 doesn't do anything to the tree; it remains the same.

Further testing shows that if I had removed 5 first and then 30, then everything works fine as well:

bst.remove(10); // this works fine and the resulting bst tree is structurally correct
bst.remove(18); // this works fine and the resulting bst tree is structurally correct
bst.remove(20); // this works fine and the resulting bst tree is structurally correct
bst.remove(22); // this works fine and the resulting bst tree is structurally correct
bst.remove(5); // Results in a tree with 30 as the root value
bst.remove(30); // Results in the empty tree where root === null


Can anyone help me understand why removing 30 initially didn't work?

Answer

Your code has a provision for the case when the found node is the root and it is the only node in the tree, and if a node has both a left and a right child, you overwrite its value. But when the node to remove is the root and it has only one child, there is nothing in your code that overwrites this.root, and you don't overwrite the root's value, so it is not removed and the tree remains unmodified.

You can fix this by changing this:

if ( node === void 0 ) node = this.root;

// compare the node's value with the value
if ( value < node.value ) {

to this:

if ( node === void 0 ) {
    this.root = this.remove(value, this.root);
// compare the node's value with the value
} else if ( value < node.value ) {

Once that is fixed, you can simplify your logic a bit:

remove: function (value, node) {
    if (!this.isEmpty()) {
        // initialize node
        if (!node) {
            this.root = this.remove(value, this.root);
        } else if (value < node.value && node.left) {
            node.left = this.remove(value, node.left);
        } else if (value > node.value && node.right) {
            node.right = this.remove(value, node.right);
        } else if (value === node.value) {
            // check if node is a leaf node
            if (node.left && node.right) {
                // node has two children. change its value to the min
                // right value and remove the min right node
                node.value = this.findMinValue(node.right);
                node.right = this.remove(node.value, node.right);
            } else {
                // replace the node with whichever child it has
                node = node.left || node.right;
            }
        }
        return node;
    }
},

and then you can simplify it further by separating it into two methods:

remove: function (value) {
    this.root = this._removeInner(value, this.root);
},

_removeInner: function (value, node) {
    if (node) {
        if (value < node.value) {
            node.left = this._removeInner(value, node.left);
        } else if (value > node.value) {
            node.right = this._removeInner(value, node.right);
        } else if (node.left && node.right) {
            node.value = this.findMinValue(node.right);
            node.right = this._removeInner(node.value, node.right);
        } else {
            node = node.left || node.right;
        }
    }
    return node;
},

Demo


@wmock has asked how I went about solving this problem so I'll elaborate on that a bit.

The first thing I did was walk the code in the debugger, focusing on the bst.remove(30) part. I noticed that 30 was the root at that point and that it remained there after remove() was done. This led me to noticing that the code never modifies the root in that particular case.

I then looked at how the return value of this.remove() was being assigned to node.left and node.right, and with some recollection of BST algorithms, thought it would make sense to emulate that for the root as well. And that was indeed the answer.

There were a few things that motivated splitting the method into two methods:

  • I noticed that the method had a fair amount of special-case functionality that was only relevant for the initial call to bst.remove()
    • Checking this.isEmpty()
    • Using this.root for the value of node if node was null
    • Resetting this.root to null under certain cases when the tree height is 0

It seemed sloppy to be doing all of that in every pass through remove()

  • I also repeatedly found myself wanting to use if (!node) to check whether I had reached the edge of the tree, but I couldn't because there was that special case logic to use this.root when node was null.

Splitting the method into two parts resolved all of the above issues.

Note that in a lot of BST implementations, the functionality in _removeInner() would be a method on the binaryTreeNode type, and the tree would just interact with the root node. That eliminates the need to pass a node from one method call to the next:

In binarySearchTree:

remove: function (value) {
    this.root && this.root.remove(value);
},

In binaryTreeNode:

remove: function (value) {
    if (value < this.value) {
        this.left = this.left && this.left.remove(value);
    } else if (value > this.value) {
        this.right = this.right && this.right.remove(value);
    } else if (this.left && this.right) {
        this.value = this.right.findMinValue();
        this.right = this.right.remove(this.value);
    } else {
        return this.left || this.right;
    }
    return this;
},

findMinValue: function () {
    return this.left ? this.left.findMinValue() : this.value;
}

Demo