Breadth First Search
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174
class Node {
constructor(value){
this.left = null;
this.right = null;
this.value = value;
}
}
class BinarySearchTree {
constructor(){
this.root = null;
}
insert(value){
const newNode = new Node(value);
if (this.root === null) {
this.root = newNode;
} else {
let currentNode = this.root;
while(true){
if(value < currentNode.value){
//Left
if(!currentNode.left){
currentNode.left = newNode;
return this;
}
currentNode = currentNode.left;
} else {
//Right
if(!currentNode.right){
currentNode.right = newNode;
return this;
}
currentNode = currentNode.right;
}
}
}
}
lookup(value){
if (!this.root) {
return false;
}
let currentNode = this.root;
while(currentNode){
if(value < currentNode.value){
currentNode = currentNode.left;
} else if(value > currentNode.value){
currentNode = currentNode.right;
} else if (currentNode.value === value) {
return currentNode;
}
}
return null
}
// remove
remove(value){
if(!this.root){
return false;
}
let currentNode=this.root;
let parentNode=null;
while(currentNode){
if(value<currentNode.value){
parentNode=currentNode;
currentNode=currentNode.left;
}
else if (value>currentNode.value){
parentNode=currentNode;
currentNode=currentNode.right;
}
else if(value===currentNode.value){
//if it has no right child
if(currentNode.right===null){
if(parentNode===null){
this.root=currentNode.left
}else{
if(currentNode.value<parentNode.value){
parentNode.left=currentNode.left;
}
else if(currentNode.value>parentNode.value){
parentNode.right=currentNode.left;
}
}
}
else if(currentNode.right.left===null){
currentNode.right.left=currentNode.left;
if(parentNode===null){
this.root=currentNode.right;
}
else{
if(currentNode.value<parentNode.value){
parentNode.left=currentNode.right;
}
else if(currentNode.value>parentNode.value){
parentNode.right=currentNode.right
}
else{
let leftmost=currentNode.right.left;
let leftmostParent=currentNode.right;
while(leftmost!==null){
leftmostParent=leftmost;
leftmost=leftmost.left;
}
leftmostParent.left=leftmost.right;
leftmost.left=currentNode.left;
leftmost.right=currentNode.right;
if(parentNode===null){
this.root=leftmost;
}
else{
if(currentNode.value<parentNode.value){
parentNode.left=leftmost;
}
else if(currentNode.value>parentNode.value){
parentNode.right=leftmost;
}
}
}
return false;
}
}
}
}
}
breadthFirstSearch(){
let currentNode=this.root;
let list=[];
let queue=[];
queue.push(currentNode);
while(queue.length>0){
currentNode=queue.shift();
list.push(currentNode);
if (currentNode.left){
queue.push(currentNode.left);
}
if(currentNode.right){
queue.push(currentNode.right);
}
}
return list;
}
}
const tree = new BinarySearchTree();
tree.insert(9)
tree.insert(4)
tree.insert(6)
tree.insert(20)
tree.insert(170)
tree.insert(15)
tree.insert(1)
// JSON.stringify(traverse(tree.root))
tree.lookup(15);
tree.lookup(7);
tree.breadthFirstSearch();
// 9
// 4 20
//1 6 15 170
function traverse(node) {
const tree = { value: node.value };
tree.left = node.left === null ? null : traverse(node.left);
tree.right = node.right === null ? null : traverse(node.right);
return tree;
}
JavaScript
INFO