Binary Tree Implementation
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179
class Node {
constructor(value){
this.left = null;
this.right = null;
this.value = value;
}
}
class BinarySearchTree {
constructor(){
this.root = null;
}
insert(value){
//Code here
const node = new Node(value);
if(!this.root){
this.root = node;
return this;
}
let currentNode = this.root;
while(true){
if(currentNode.value > value){
if(!currentNode.left){
currentNode.left = node;
return this;
}
currentNode = currentNode.left
} else {
if(!currentNode.right){
currentNode.right = node;
return this;
}
currentNode = currentNode.right
}
}
}
lookup(value){
//Code here
if(!this.root){
return null;
}
let currentNode = this.root;
while(true){
if(currentNode.value == value){
return currentNode;
}
if(currentNode.value > value){
if(!currentNode.left){
return null;
}
currentNode = currentNode.left
} else {
if(!currentNode.right){
return null;
}
currentNode = currentNode.right
}
}
}
// remove
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){
queue.push(currentNode.left);
}
if(currentNode.right){
queue.push(currentNode.right);
}
}
return list;
}
breadthFirstSearchRecursive(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.breadthFirstSearchRecursive(queue, list);
}
dfsInOrder(currentNode, list){
if(currentNode.left){
this.dfsInOrder(currentNode.left, list);
}
list.push(currentNode.value);
if(currentNode.right){
this.dfsInOrder(currentNode.right, list);
}
return list;
}
dfsPostOrder(currentNode, list){
if(currentNode.left){
this.dfsPostOrder(currentNode.left, list);
}
if(currentNode.right){
this.dfsPostOrder(currentNode.right, list);
}
list.push(currentNode.value);
return list;
}
dfsPreOrder(currentNode, list){
list.push(currentNode.value);
if(currentNode.left){
this.dfsPreOrder(currentNode.left, list);
}
if(currentNode.right){
this.dfsPreOrder(currentNode.right, list);
}
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)
tree.lookup(170);
tree.breadthFirstSearch();
tree.breadthFirstSearchRecursive([tree.root], []);
tree.dfsPostOrder(tree.root, [])
//JSON.stringify(traverse(tree.root))
// 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