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
if(children===1){
let isChild = target.left?‘left’:‘right’;
if(target === parent.left){
parent.left=target[isChild];
}else{
parent.right=target[isChild];
}
}
if(children===2){
// if the node to be deleted is the root node;
if(!parent){
let temp=target;
console.log(temp.right);
target = findMin(temp.right);
console.log(target);
deleteMin(temp.right,target.value);
console.log(temp.right.value);
this.root = target;
this.root.left=temp.left;
this.root.right =temp.right;
return;
}
let temp = target;
target = findMin(temp);
deleteMin(temp,target.value);
target.left = temp.left;
target.right = temp.right;
const dir = parent.left===temp?‘left’:‘right’;
parent[dir]=target;
}
// Only change code below this line
};
}
function findMin(root){
if(!root.left){
return root ;
}
return findMin(root.left);
}
function deleteMin (root,val){
console.log(root.value,‘min’,val);
let target=root;
let parent;
while(target&&target.value!==val){
parent=target;
if(val>target.value){
target=target.right;
}
if(val<target.value){
target=target.left;
}
}
const dir=parent.left===target?‘left’:‘right’;
parent[dir]= null;
}
let node = new Node(50);
let left = new Node(30);
let right = new Node(70);
node.left=left;
node.right=right;
let rightLeft = new Node(60);
let rightRight = new Node(80);
node.right.left = rightLeft;
node.right.right = rightRight;
let leftLeft = new Node(20);
let leftRight = new Node(40);
node.left.left=leftLeft;
node.left.right = leftRight;
let inOrde =
function inOrder (root){
if(!root){
return;
}
inOrder(root.left);
inOrde.push(root.value);
inOrder(root.right);
}
// console.log(findMin(node.right));
let bs = new BinarySearchTree();
bs.root=node;
bs.remove(80);
inOrder(bs.root);
displayTree(bs);
console.log(bs.root.value);
console.log(inOrde);