Deleting Node from BinarySearchTree with two children

Contributors
1
Solution 
function BinarySearchTree() {
  this.root = null;
  this.remove = function(value) {
    if (this.root === null) {
      return null;
    }
    var target;
    var parent = null;
    // find the target value and its parent
    (function findValue(node = this.root) {
      if (value == node.value) {
        target = node;
      } else if (value < node.value && node.left !== null) {
        parent = node;
        return findValue(node.left);
      } else if (value < node.value && node.left === null) {
        return null;
      } else if (value > node.value && node.right !== null) {
        parent = node;
        return findValue(node.right);
      } else {
        return null;
      }
    }.bind(this)());
    if (target === null) {
      return null;
    }
    // count the children of the target to delete
    var children =
      (target.left !== null ? 1 : 0) + (target.right !== null ? 1 : 0);
    // case 1: target has no children
    if (children === 0) {
      if (target == this.root) {
        this.root = null;
      } else {
        if (parent.left == target) {
          parent.left = null;
        } else {
          parent.right = null;
        }
      }
    }
    // case 2: target has one child
    else if (children == 1) {
      var newChild = target.left !== null ? target.left : target.right;
      if (parent === null) {
        target.value = newChild.value;
        target.left = null;
        target.right = null;
      } else if (newChild.value < parent.value) {
        parent.left = newChild;
      } else {
        parent.right = newChild;
      }
      target = null;
    }
    *// case 3: target has two children, change code below this line*
*    else {*
*      let lowest*
*      let lowestParent = target*
*      function smallest(node) {*
*        if (node.left) {*
*          lowestParent = node*
*          smallest(node.left)*
*        } else {*
*          lowest = node*
*          return*
*        }*
*      }*
*      smallest(target.right)*
*      if (lowestParent == target) {*
*        lowestParent.right = null*
*      } else {*
*        lowestParent.left = null*
*      }*
*      target.value = lowest.value*
*    }*
  };
}

Link to the challenge:

2

Welcome, peter.

Thank you, for this contribution. Could you explain why you have the asterisks (*) around the code of one section?

To other contributors with more knowledge confirm: Is the value word reserved in JavaScript? (In which case, we should change it) I just wonder, because the syntax highlighting seems to think it is a keyword.

3

it is reserved, it has a default value of empty string

not on node, so it’s a browser thing

1 Like
4

Hey Sky,

The asterisks are just to highlight my part of the solution. The rest is provided by the challenge.