Delete a Node with Two Children in a Binary Search Tree test bug?

JavaScript
1

Hi,

I noticed that the second last test is passing without adding the remove method for a target with two children (case 3 two children, see picture). Am I misunderstanding something or this is a bug? This is not a big deal, but people could assume their code is fine when isn’t …

Screenshot_2019-12-30%20Learn%20Data%20Structures%20Delete%20a%20Node%20with%20Two%20Children%20in%20a%20Binary%20Search%20Tree%20freeCodeCamp%20org
Screenshot_2019-12-30%20Learn%20Data%20Structures%20Delete%20a%20Node%20with%20Two%20Children%20in%20a%20Binary%20Search%20Tree%20freeCodeCamp%20org1332×320 26.4 KB

Indeed, if I added the code to remove only the case with three nodes, I managed to pass all the tests and therefore the lesson/question (all tests ticked).
Cheers

Screenshot_2019-12-30%20Learn%20Data%20Structures%20Delete%20a%20Node%20with%20Two%20Children%20in%20a%20Binary%20Search%20Tree%20freeCodeCamp%20org(1)
Screenshot_2019-12-30%20Learn%20Data%20Structures%20Delete%20a%20Node%20with%20Two%20Children%20in%20a%20Binary%20Search%20Tree%20freeCodeCamp%20org(1)1312×287 24.4 KB

3

Hi Randell,

You can run the code as is given in the challenge (you can see in the first picture that no code is added after the green line indicating case 3).
If I add the particular case for three node pases all the tests (the last else is commented in purpose):

var displayTree = tree => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

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{ // This is only for the three nodes
      if(target == this.root){
        this.root = target.left;
        this.root.left = null;
        this.root.right = target.right;
      }
    }
  };
}

Sorry, not familiar with the forum, let me know if I need to format anything or add more information …

1 Like