| class Node { | |
| constructor(value){ | |
| this.value = value; | |
| this.left = null; | |
| this.right = null; | |
| } | |
| } | |
| class BinarySearchTree { | |
| constructor() { | |
| this.root = null; | |
| } | |
| insert(value) { | |
| let newNode = new Node(value); | |
| if(!this.root) { | |
| this.root = newNode; | |
| return this; | |
| } | |
| let currentNode = this.root; | |
| while(true) { | |
| if(newNode.value === currentNode.value) return undefined; | |
| if(newNode.value > currentNode.value) { | |
| if(currentNode.right === null) { | |
| currentNode.right = newNode | |
| return this; | |
| } else { | |
| currentNode = currentNode.right; | |
| } | |
| } else if(newNode.value < currentNode.value) { | |
| if(currentNode.left === null) { | |
| currentNode.left = newNode; | |
| return this; | |
| } else { | |
| currentNode = currentNode.left; | |
| } | |
| } | |
| } | |
| // let prevNode = currentNode; | |
| // if(newNode.value > currentNode.value) { | |
| // currentNode = currentNode.right; | |
| // } else { | |
| // currentNode = currentNode.left; | |
| // } | |
| // while(currentNode) { | |
| // prevNode = currentNode; | |
| // if(newNode.value > currentNode) { | |
| // currentNode = currentNode.right; | |
| // } else { | |
| // currentNode = currentNode.left; | |
| // } | |
| // } | |
| // if(newNode.value > prevNode.value) { | |
| // prevNode.right = newNode | |
| // } else { | |
| // prevNode.left = newNode | |
| // } | |
| // return this; | |
| } | |
| find(value) { | |
| let currentNode = this.root; | |
| while(currentNode) { | |
| if(value === currentNode.value) return currentNode; | |
| if(value < currentNode.value) { | |
| currentNode = currentNode.left | |
| } else { | |
| currentNode = currentNode.right | |
| } | |
| } | |
| return undefined; | |
| } | |
| contains(value) { | |
| let currentNode = this.root; | |
| while(currentNode) { | |
| if(value === currentNode.value) return true; | |
| if(value < currentNode.value) { | |
| currentNode = currentNode.left | |
| } else { | |
| currentNode = currentNode.right | |
| } | |
| } | |
| return false; | |
| } | |
| BreadthFirstSearch() { | |
| if(!this.root) return []; | |
| let queue = []; | |
| let visited = []; | |
| let node; | |
| queue.push(this.root); | |
| while(queue.length > 0){ | |
| node = queue.shift(); | |
| visited.push(node.value) | |
| if(node.left) { | |
| queue.push(node.left) | |
| } | |
| if(node.right) { | |
| queue.push(node.right) | |
| } | |
| } | |
| return visited; | |
| } | |
| DepthFirstSearchPreOrder() { | |
| let visited = []; | |
| function traverse(node) { | |
| visited.push(node.value) // pre order logic | |
| if(node.left) { | |
| traverse(node.left) | |
| } | |
| if(node.right){ | |
| traverse(node.right) | |
| } | |
| } | |
| traverse(this.root); | |
| return visited; | |
| } | |
| DepthFirstSearchPostOrder() { | |
| let visited = []; | |
| function traverse(node) { | |
| if(node.left) { | |
| traverse(node.left) | |
| } | |
| if(node.right){ | |
| traverse(node.right) | |
| } | |
| visited.push(node.value) // post order logic | |
| } | |
| traverse(this.root); | |
| return visited; | |
| } | |
| DepthFirstSearchInOrder() { | |
| let visited = []; | |
| function traverse(node) { | |
| if(node.left) { | |
| traverse(node.left) | |
| } | |
| visited.push(node.value) // in order logic | |
| if(node.right){ | |
| traverse(node.right) | |
| } | |
| } | |
| traverse(this.root); | |
| return visited; | |
| } | |
| } | |
| let bst = new BinarySearchTree(); | |
| // 10 | |
| // 5 13 | |
| //2 7 11 16 | |
| bst.insert(10).insert(5).insert(13).insert(7).insert(2).insert(16).insert(11) |