Deep First Search
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250
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(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 (currentNode.value === value) {
//We have a match, get to work!
//Option 1: No right child:
if (currentNode.right === null) {
if (parentNode === null) {
this.root = currentNode.left;
} else {
//if parent > current value, make current left child a child of parent
if(currentNode.value < parentNode.value) {
parentNode.left = currentNode.left;
//if parent < current value, make left child a right child of parent
} else if(currentNode.value > parentNode.value) {
parentNode.right = currentNode.left;
}
}
//Option 2: Right child which doesnt have a left child
} else if (currentNode.right.left === null) {
currentNode.right.left = currentNode.left;
if(parentNode === null) {
this.root = currentNode.right;
} else {
//if parent > current, make right child of the left the parent
if(currentNode.value < parentNode.value) {
parentNode.left = currentNode.right;
//if parent < current, make right child a right child of the parent
} else if (currentNode.value > parentNode.value) {
parentNode.right = currentNode.right;
}
}
//Option 3: Right child that has a left child
} else {
//find the Right child's left most child
let leftmost = currentNode.right.left;
let leftmostParent = currentNode.right;
while(leftmost.left !== null) {
leftmostParent = leftmost;
leftmost = leftmost.left;
}
//Parent's left subtree is now leftmost's right subtree
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 true;
}
}
}
breadthFristSearch(){
let currentNode = this.root;
let list = [];
let queue = [];
queue.push(currentNode);
while(queue.length > 0){
currentNode = queue.shift();
console.log(currentNode);
console.log(currentNode.value);
list.push(currentNode.value);
if(currentNode.left){
queue.push(currentNode.left);
}
if(currentNode.right){
queue.push(currentNode.right);
}
}
return list;
}
breadthFristSearchR( queue, list ){
if(!queue.length){
return list;
}
let currentNode = queue.shift();
list.push(currentNode.value)
if(currentNode.left){
queue.push(currentNode.left);
}
if(currentNode.right){
queue.push(currentNode.right);
}
return this.breadthFristSearchR(queue,list);
}
DFSInorder(){
return traverseInOrder(this.root,[]);
}
DFSPostOrder(){
return traversePostOrder(this.root,[]);
}
DFSPreorder(){
return traversePreOrder(this.root,[]);
}
}
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)
//tree.remove(170)
//console.log(JSON.stringify(traverse(tree.root)));
console.log(tree.DFSInorder());
console.log(tree.DFSPreorder());
console.log(tree.DFSPostOrder());
// 9
// 4 20
//1 6 15 170
//InOrder = [1,4,6,9, 15, 20,170 ]
//PreOrder = [9,4,1,6, 20, 15,170 ]
//PostOrder = [1,6,4,15,170,20,9 ]
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;
}
function traverseInOrder(node,list){
if(node.left){
traverseInOrder(node.left,list);
}
list.push(node.value);
if(node.right){
traverseInOrder(node.right,list);
}
return list;
}
function traversePreOrder(node,list){
list.push(node.value);
if(node.left){
traversePreOrder(node.left,list);
}
if(node.right){
traversePreOrder(node.right,list);
}
return list;
}
function traversePostOrder(node,list){
if(node.left){
traversePostOrder(node.left,list);
}
if(node.right){
traversePostOrder(node.right,list);
}
list.push(node.value);
return list;
}
JavaScript
INFO