Tell us what’s happening:
Hi, guys.
I am really stuck with this challenge. I could not pass the test ‘The root can be removed on a tree of three nodes’.
Help please.
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;
}
return;
}
let least = target.right;
let 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;
}
}
}
};
}
Your browser information:
User Agent is: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_14_5) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/75.0.3770.142 Safari/537.36.
Link to the challenge:
https://learn.freecodecamp.org/coding-interview-prep/data-structures/delete-a-node-with-two-children-in-a-binary-search-tree