Delete a Node with Two Children in a Binary Search Tree

Delete a Node with Two Children in a Binary Search Tree
0

Tell us what’s happening:

Your code so far


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{
        if(target.left&&target.right&&!target.left.left&&!target.left.right&&!target.right.left&&!target.right.right){
          console.log(JSON.stringify(target))
          if(target===this.root){
            this.root=null;
          }else{
            target=null
          }
          console.log(JSON.stringify(target))
          return
        }

      var least = target.right;
      var parent=target;
      while(true){
        
        if(least.left){
          parent=least;
          least=least.left
        }else{
          if(!least.right){
            parent.left=null;
            least.left=target.left;
            least.right=target.right
            least.value=target.value;
            target=null;
          }else{
            parent.left=least.right;
            least.right=target.right;
            least.left =target.left
            least.value=target.value
            target=null;
          }

          break;
        }
        
      }
      console.log(JSON.stringify(least))
    }
  };
}

var test = new BinarySearchTree()

test.root = new Node(10)
test.root.left = new Node(7)
test.root.right = new Node(15)
// test.root.right.left = new Node(13);
// test.root.right.left.right = new Node(14);
testremove(10)

displayTree(test)

Link to the challenge:
https://learn.freecodecamp.org/coding-interview-prep/data-structures/delete-a-node-with-two-children-in-a-binary-search-tree

Again test isn’t checking properly. The root can be removed on a tree of three nodes. test is not passing at all yet manual tests say it otherwise.

Code part:

    // case 3: target has two children, change code below this line
    else{
        if(target.left&&target.right&&!target.left.left&&!target.left.right&&!target.right.left&&!target.right.right){
          console.log(JSON.stringify(target))
          if(target===this.root){
            this.root=null;
          }else{
            target=null
          }
          console.log(JSON.stringify(target))
          return
        }

I’m struck with this challenge. Can you help me with this?