Clever Geek Handbook

JavaScript Binary Tree Search - Remove a Function

Here's my implementation for a binary search tree in JavaScript. All functions work correctly except for the function remove

. In particular, it seems to be deleting nodes correctly until there are 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 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 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 a binary search tree works great:

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

I am facing a problem where I remove the value every time root

:

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

Before deleting 30, the tree only has two values: 30 as the root value and 5 as the root.left value. I would expect that deleting 30 would give me a tree that has 5 as its root. However, deleting 30 does nothing to the tree; it remains the same.

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

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?

+3


source to share


3 answers


There is a condition in your code for the case where the found node is root and it is the only node in the tree, and if the node has both left and right children, you overwrite its value. But when the node to be deleted is the root and it only has one child, there is nothing in your code that overwrites this.root

, and you don't overwrite the root value, so it is not deleted and the tree remains unchanged.

You can fix this by changing this:

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

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

:

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

Once that's 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 by splitting 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 asked how I went about solving this problem, so I thought about it a bit.

The first thing I did was go through the code in the debugger, focusing on the part bst.remove(30)

. I noticed that 30 was root at that point and that it stayed there after remove()

. This made me notice that the code never changes the root in this particular case.



Then I looked at how the return value this.remove()

was assigned node.left

and node.right

, and with some recollection of the BST algorithms, I thought it made sense to emulate that for the root. And that was really the answer.

There were several things that motivated the separation of the method into two methods:

  • I noticed that this method has a fair amount of special functions, which was only relevant for the initial call bst.remove()

    • Check this.isEmpty()

    • Using this.root

      for value node

      if node

      was null
    • Reset this.root

      to zero in certain cases when tree height is 0

It seems careless to do it all in every pass through remove()

  • I also found myself repeatedly what I want to use if (!node)

    to check if I have reached the edge of the tree, but I could not, because in that case special case logic was used this.root

    when it node

    was null.

Splitting the method into two parts solved all of the above problems.

Note that in many BST implementations the functionality in _removeInner()

will be a type method binaryTreeNode

and the tree will simply interact with the root node. This removes the need to pass 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

+6


source


Here is a complete example of a binary tree with insert and remove functionality

function Node(val) {
    this.data = val;
    this.right = null;
    this.left = null;
}

function BST() {
    this.root = null;
    this.insert = insert;
    this.inOrder = inOrder;
    this.remove = remove;
    this.removeNode = removeNode;
    this.kthSmallestNode = kthSmallestNode;
}

function insert(val) {
    if (val == null || val == undefined)
        return;

    if (this.root == null) {
        this.root = new Node(val);
        return;
    }

    var current = this.root
    var newNode = new Node(val);

    while (true) {
        if (val < current.data) {
            if (current.left == null) {
                current.left = newNode;
                return;
            }
            current = current.left;
        } else {
            if (current.right == null) {
                current.right = newNode;
                return;
            }
            current = current.right;
        }
    }

}

function remove(val) {
    this.root = removeNode(this.root, val);
}

function removeNode(current, value) {
    if (value == null || value == undefined)
        return;

    if (value == current.data) {
        if (current.left == null && current.right == null) {
            return null;
        } else if (current.left == null)
            return current.right;
        else if (current.right == null)
            return current.left;
        else {
            var tempNode = kthSmallestNode(current.right);
            current.data = tempNode.data;
            current.right = removeNode(current.right, tempNode.data);
            return current;
        }


    } else if (value < current.data) {
        current.left = removeNode(current.left, value);
        return current;
    } else {
        current.right = removeNode(current.right, value);
        return current;
    }
}

function kthSmallestNode(node) {
    while (!(node.left == null))
        node = node.left;

    return node;
}

function inOrder(node) {
    if (!(node == null)) {
        inOrder(node.left);
        console.log(node.data + " ");
        inOrder(node.right);
    }
}


var tree = new BST();
tree.insert(25);
tree.insert(20);
tree.insert(30);
tree.insert(27);
tree.insert(21);
tree.insert(16);
tree.insert(26);
tree.insert(35);

tree.remove(30)

console.log("Inorder : ")
console.log(tree.inOrder(tree.root))


Luck!!!

+2


source


I have a rather simplified answer that I think most people will understand, and it takes child nodes into account. The key is that if you delete a value with a right and left child, you go left first and then all the way to the right, because this will ensure it has no children and is easier to update.

  removeNode(val) {
    let currentNode, parentNode, nextBiggestParentNode=null, found=false, base=[this.root];
    while(base.length > 0 && !found) {
      currentNode = base.pop();
      if(currentNode.value === val) {
        found=true;
        if(!currentNode.left && !currentNode.right) {
          parentNode.right === currentNode ? parentNode.right = null : parentNode.left = null;
        }
        else if(!currentNode.right && currentNode.left) {
          parentNode.right === currentNode ? parentNode.right = currentNode.left : parentNode.left = currentNode.left;
        }
        else if(!currentNode.left && currentNode.right) {
          parentNode.right === currentNode ? parentNode.right = currentNode.right : parentNode.left = currentNode.right;
        }
        else {
          let _traverse = node => {
            if (node.right) {
              nextBiggestParentNode = node;
              _traverse(node.right);
            }
            else {
              currentNode.value = node.value;
              nextBiggestParentNode ? nextBiggestParentNode.right = null : currentNode.left = null;
            }
          }
          _traverse(currentNode.left);
        }
      }
      else {
        parentNode = currentNode;
        val > currentNode.value && currentNode.right ? base.unshift(currentNode.right) : base.unshift(currentNode.left);
      }
    }
    return this;
  }

this code is part of the class, here is the rest of my constructor code in case anyone is interested.

let TreeNode = class  {
  constructor(value, left=null, right=null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

let BST = class {
  constructor(root=null) {
    this.root = root;
  }

  insert(nodeToInsert) {
    if (this.root === null) {
      this.root = nodeToInsert;
    } else {
      this._insert(this.root, nodeToInsert);
    }
  }

  _insert(root, nodeToInsert) {
    if (nodeToInsert.value < root.value) {
      if (!root.left) {
        root.left = nodeToInsert;
      } else {
        this._insert(root.left, nodeToInsert);
      }
    } else {
      if (!root.right) {
        root.right = nodeToInsert;
      } else {
        this._insert(root.right, nodeToInsert);
      }
    }
  }

here is some demo code to create bst and remove value

let bst = new BST();
const nums = [20,10,5,15,3,7,13,17,30,35,25,23,27,37,36,38];
function createBst() {
  for (let i of nums) {
    bst.insert(new TreeNode(i));
  }
  console.log(JSON.stringify(bst, null, 2));
  bst.removeNode(35);
}
createBst();
console.log(JSON.stringify(bst, null, 2));
0


source






More articles:


All Articles