BFS
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186
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;
}
}
}
breadthFirstSearch() {
let currentNode = this.root;
let list = [];
let queue = [];
queue.push(currentNode);
while (queue.length > 0) {
currentNode = queue.shift();
list.push(currentNode.value);
if (currentNode.left !== null) {
queue.push(currentNode.left);
}
if (currentNode.right !== null) {
queue.push(currentNode.right);
}
}
return list;
}
breadthFirstSearchRecursive(queue, list) {
if (queue.length === 0) {
return list;
}
let currentNode = queue.shift();
list.push(currentNode.value);
if (currentNode.left !== null) {
queue.push(currentNode.left);
}
if (currentNode.right !== null) {
queue.push(currentNode.right);
}
return this.breadthFirstSearchRecursive(queue, list);
}
}
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;
}
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(JSON.stringify(traverse(tree.root)));
console.log(tree.breadthFirstSearch());
console.log(tree.breadthFirstSearchRecursive([tree.root], []));
JavaScript
INFO