Implementation of Binary Search Tree

Run Settings
LanguageJavaScript
Language Version
Run Command
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; } } } } } } 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); // 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; }
Editor Settings
Theme
Key bindings
Full width
Lines