class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
let node = new Node(value);
if (this.root === null) {
this.root = node;
return this;
}
let curr = this.root;
while(curr !== null) {
if (value > curr.value) {
if (curr.right) {
curr = curr.right;
} else {
curr.right = node;
return;
}
} else {
if (curr.left) {
curr = curr.left;
} else {
curr.left = node;
return;
}
}
}
}
lookup(value) {
if (this.root === null) {
return null;
}
let curr = this.root;
while (curr !== null ) {
if (value > curr.value) { // go right
if (curr.right) {
curr = curr.right;
} else {
return null;
}
} else if( value < curr.value) { // go left, ie value is less than curr.value
if (curr.left) {
curr = curr.left;
} else {
return null;
}
} else { // if value == curr.value
return curr;
}
}
}
remove(value) {
if (this.root === null) {
return null;
}
let parent = this.root;
let curr = this.root;
let left = this.root.left;
let right = this.root.right;
while (curr !== null ) {
console.log(curr.value);
if (value > curr.value) {
console.log("going right");
parent = curr;
curr = curr.right;
left = curr.left;
right = curr.right;
} else if (value < curr.value) {
console.log("going left");
parent = curr;
curr = curr.left
left = curr.left;
right = curr.right;
} else if (curr.value === value) {
if (curr.left === null && curr.right === null) { // leaf node
if (value < parent.value) {
parent.left = null;
} else {
parent.right = null;
}
return curr;
}
if (curr.right.left === null && curr.right.right === null) {
parent.right = curr.right;
parent.right.left = left;
return curr;
}
if (curr.right.left === null && curr.right.right !== null) {
parent.right = curr.right;
parent.right.left = left;
return curr;
}
if (curr.right.left !== null && curr.right.right === null) {
parent.right = curr.right.left;
parent.right.right = curr.right;
parent.right.left = curr.left;
curr.right.left = null;
}
curr = null;
}
}
}
preorderTraversal(node, list) {
list.push(node.value);
if (node.left !== null) {
this.preorderTraversal(node.left, list);
}
if (node.right !== null) {
this.preorderTraversal(node.right, list);
}
return list;
}
postorderTraversal(node, list) {
if (node.left !== null) {
this.postorderTraversal(node.left, list);
}
if (node.right !== null) {
this.postorderTraversal(node.right, list);
}
list.push(node.value);
return list;
}
inorderTraversal(node, list) {
if (node.left !== null) {
this.inorderTraversal(node.left, list);
}
list.push(node.value);
if (node.right !== null) {
this.inorderTraversal(node.right, list);
}
return list;
}
}
const tree = new BinarySearchTree();
tree.insert(9);
tree.insert(4);
tree.insert(20);
tree.insert(1);
tree.insert(6);
tree.insert(15);
tree.insert(170);
// tree.insert(180);
// tree.insert(179);
// tree.insert(181);
// tree.insert(150);
// console.log(tree.remove(20));
console.log("inorderTraversal: ");
console.log(tree.inorderTraversal(tree.root, []));
console.log("preorderTraversal: ");
console.log(tree.preorderTraversal(tree.root, []));
console.log("postorderTraversal: ");
console.log(tree.postorderTraversal(tree.root, []));
