Binary Search Tree
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BST {
constructor(value) {
if(typeof value !== "undefined") {
this.root = new TreeNode(value);
}else {
this.root = null;
}
}
insert(value) {
if(this.root === null) {
this.root = new TreeNode(value);
}else {
let cur = this.root;
while(cur !== null) {
if(value >= cur.value) {
if(cur.right === null) {
cur.right = new TreeNode(value);
return this;
}else {
cur = cur.right;
}
}else {
if(cur.left === null) {
cur.left = new TreeNode(value);
return this;
}else {
cur = cur.left;
}
}
}
}
return this;
}
lookup(value) {
if(this.root === null) {
return false;
}else {
let cur = this.root;
while(cur !== null) {
if(value === cur.value) {
return cur;
}else if(value > cur.value) {
cur = cur.right;
}else {
cur = cur.left;
}
}
return false;
}
}
removeNode(value) {
if(this.root === null) {
return false;
}else {
if(this.root.value === value) {
const sucNode = this.getSuccessor(this.root);
if(sucNode !== null) {
sucNode.left = this.root.left;
sucNode.right = this.root.right;
}
this.root = sucNode;
return this;
}else {
let cur = this.root;
while(cur !== null) {
if(value === cur.left) {
const sucNode = this.getSuccessor(cur.left);
if(sucNode !== null) {
sucNode.left = cur.left.left;
sucNode.right = cur.left.right;
}
cur.left = sucNode;
return this;
}else if(value === cur.right) {
const sucNode = this.getSuccessor(cur.right);
if(sucNode !== null) {
sucNode.left = cur.right.left;
sucNode.right = cur.right.right;
}
cur.right = sucNode;
return this;
}else if(value < cur.value) {
cur = cur.left;
}else {
cur = cur.right;
}
}
return false;
}
}
}
getSuccessor(node) {
if(node.left === null) {
if(node.right === null) {
return null;
}else {
const temp = node.right;
node.right = null;
return temp;
}
}else if(node.right === null) {
const temp = node.left;
node.left = null;
return temp;
}else {
if(node.right.left === null) {
const temp = node.right;
node.right = null;
return temp;
}else {
let cur = node.right;
while(cur.left.left !== null) {
cur = cur.left;
}
const temp = cur.left;
cur.left = null
return temp;
}
}
}
inOrderTraversal() {
function trav(node) {
if(node === null) {
return null;
}
trav(node.left);
console.log(node.value);
trav(node.right);
}
trav(this.root);
}
breadthFirstSearchR() {
if(this.root === null) {
return null;
}
function trav(nodeQueue) {
if(nodeQueue.length === 0) {
return;
}
const node = nodeQueue.shift();
console.log(node.value);
if(node.left !== null) {
nodeQueue.push(node.left);
}
if(node.right !== null) {
nodeQueue.push(node.right);
}
return trav(nodeQueue);
}
const queue = [this.root];
trav(queue);
}
breadthFirstSearchI() {
if(this.root === null) {
return null;
}
const nodeQueue = [this.root];
while(nodeQueue.length > 0) {
const node = nodeQueue.shift();
console.log(node.value);
if(node.left !== null) {
nodeQueue.push(node.left);
}
if(node.right !== null) {
nodeQueue.push(node.right);
}
}
}
}
const bst1 = new BST(5);
bst1.insert(8);
bst1.insert(7);
bst1.insert(9);
bst1.insert(3);
bst1.insert(4);
bst1.insert(2);
bst1.inOrderTraversal();
console.log("BST Recursive");
bst1.breadthFirstSearchR();
console.log("BST Iterative");
bst1.breadthFirstSearchI();
JavaScript
INFO