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
}