I completed the remove() method to delete with two children. This is Fails on test too while as I see delete well the node…
Is anyone can take a look to
my code
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.add = function(value) {
const newNode = new Node(value);
this.root === null
? this.root = newNode
: this.insertNode(this.root, newNode)
;
};
this.insertNode = function(node, newNode) {
if (newNode.value < node.value) {
node.left === null
? node.left = newNode
: this.insertNode(node.left, newNode)
;
} else {
node.right === null
? node.right = newNode
: this.insertNode(node.right, newNode)
;
}
};
this.findMin = function(targetNode = this.root) {
if (!(targetNode)) return null;
let node = targetNode;
while (node.left) {
node = node.left;
}
return node.value;
};
this.findMax = function() {
if (!(this.root)) return null;
let node = this.root;
while (node.right) {
node = node.right;
}
return node.value;
};
this.isPresent = function(value) {
const findValue = function(node, value) {
if (!(node)) {
result = false;
return;
}
if (node.value === value) {
result = true;
return;
}
if (node.value < value) {
findValue(node.right, value);
} else {
findValue(node.left, value);
}
};
let result = false;
if (value === undefined ||
this.root === null ||
!(Number.isInteger(value)) ) {
return false;
}
findValue(this.root, value);
return result;
};
let distance, minDistance, maxDistance;
const countStep = node => {
// console.log(node.value, "on level", distance);
if (!(node.left) && !(node.right)){
// this is a leaf node
// console.log("leaf node", node.value, "on level", distance);
if (minDistance > distance) minDistance = distance;
if (maxDistance < distance) maxDistance = distance;
distance --;
return;
}
if (node.left) {
distance ++
countStep(node.left);
}
if (node.right) {
distance ++;
countStep(node.right);
}
};
this.findMinHeight = function() {
if (!(this.root)) return -1;
distance = 1;
minDistance = Infinity;
countStep(this.root.left);
distance = 1;
countStep(this.root.right);
return minDistance;
};
this.findMaxHeight = function() {
if (!(this.root)) return -1;
distance = 1;
maxDistance = -Infinity;
countStep(this.root.left);
distance = 1;
countStep(this.root.right);
return maxDistance;
};
this.isBalanced = function() {
return (this.findMaxHeight() - this.findMinHeight()) < 2;
};
this.inorder = function(node = this.root, orderedList = []) {
if (node) {
this.inorder(node.left, orderedList);
orderedList.push(node.value);
this.inorder(node.right, orderedList);
}
return orderedList.length
? orderedList
: null;
};
this.preorder = function(node = this.root, orderedList = []) {
if (node) {
orderedList.push(node.value);
this.preorder(node.left, orderedList);
this.preorder(node.right, orderedList);
}
return orderedList.length
? orderedList
: null;
};
this.postorder = function(node = this.root, orderedList = []) {
if (node) {
this.postorder(node.left, orderedList);
this.postorder(node.right, orderedList);
orderedList.push(node.value);
}
return orderedList.length
? orderedList
: null;
};
this.orderOnLevel = function(queueList = [this.root], levelOrderList = [], left = "left", right = "right") {
while (queueList.length > 0 && queueList[0] !== null) {
const node = queueList.shift();
levelOrderList.push(node.value);
if (node[left]) queueList.push(node[left]);
if (node[right]) queueList.push(node[right]);
this.orderOnLevel(queueList, levelOrderList, left, right);
}
return levelOrderList.length
? levelOrderList
: null;
};
this.levelOrder = function() {
return this.orderOnLevel();
};
this.reverseLevelOrder = function() {
return this.orderOnLevel([this.root], [], "right", "left");
};
// this function return the parent and child node with the given value or null if the value not found:
this.findValue = function(value) {
let node = this.root;
let parentNode = node;
while (node) {
if (node.value === value) return {parent : parentNode, child: node};
parentNode = node;
if (node.value < value) {
node = node.right;
} else {
node = node.left;
}
}
return null;
};
this.remove = function(value) {
const rootNode = this.root;
// if the value miss or incorrect or have not rootNode:
if (value === undefined ||
typeof value !== "number" ||
!(Number.isInteger(value)) ||
!(rootNode)) {
return null;
}
// if we have only one node:
if (rootNode.left === null &&
rootNode.right === null) {
return rootNode.value === value
? this.root = null
: null;
}
const parentAndChild = this.findValue(value);
if (!(parentAndChild)) return null; // value not found
const parentNode = parentAndChild.parent;
const childNode = parentAndChild.child;
// leaf node:
if (childNode.left === null &&
childNode.right === null) {
if (parentNode.left.value === value) {
parentNode.left = null;
} else {
parentNode.right = null;
}
return;
}
// one child:
if (parentNode.left && parentNode.left.value === value) {
// only one child node on left side:
if (childNode.left && !(childNode.right)) {
parentNode.left = childNode.left;
} else if (childNode.right && !(childNode.left)) {
parentNode.left = childNode.right;
}
}
if (parentNode.right && parentNode.right.value === value) {
// only one child node on right side:
if (childNode.left && !(childNode.right)) {
parentNode.right = childNode.left;
} else if (childNode.right && !(childNode.left)) {
parentNode.right = childNode.right;
}
}
// two children:
if (childNode.left && childNode.right) {
const minValueOnRight = this.findMin(childNode.right);
this.remove(minValueOnRight);
childNode.value = minValueOnRight;
}
};
}
const isBinarySearchTree = tree => {
if (!(tree.root) ||
!(tree.root.hasOwnProperty("left")) ||
!(tree.root.hasOwnProperty("right"))) {
return false;
}
let result = true;
const checkValue = (parentNode) => {
if (parentNode.left) {
const leftNode = parentNode.left;
if (leftNode.value >= parentNode.value) {
result = false;
return;
} else {
checkValue(leftNode);
}
}
if (parentNode.right) {
const rightNode = parentNode.right;
if (rightNode.value <= parentNode.value) {
result = false;
return;
} else {
checkValue(rightNode);
}
}
};
checkValue(tree.root);
return result;
};
const myTree = new BinarySearchTree();
myTree.add(8);
myTree.add(3);
myTree.add(10);
myTree.add(1);
myTree.add(6);
myTree.add(14);
myTree.add(4);
myTree.add(7);
myTree.add(13);
myTree.add(5);
myTree.add(12);
//console.log(myTree.findMin());
//console.log(myTree.findMax());
//console.log(myTree.isPresent(10));
//console.log(myTree.root);
//console.log(isBinarySearchTree(myTree));
//console.log("the minimum level is:", myTree.findMinHeight());
//console.log("the maximum level is:", myTree.findMaxHeight());
//console.log(myTree.isBalanced());
//console.log(myTree.inorder());
//console.log(myTree.preorder());
//console.log(myTree.postorder());
//console.log(myTree.levelOrder());
//console.log(myTree.reverseLevelOrder());
//console.log(myTree.remove(1));
//displayTree(myTree);
console.log(myTree.remove(8));
console.log(myTree.root);