Skip to content

Instantly share code, notes, and snippets.

@bmakuh
Created April 1, 2017 22:01
Show Gist options
  • Save bmakuh/ead07338469c646898964a7877182ece to your computer and use it in GitHub Desktop.
Save bmakuh/ead07338469c646898964a7877182ece to your computer and use it in GitHub Desktop.
Binary search tree in JS
class Node {
constructor (val) {
this.value = val
this.left = null
this.right = null
}
static of (val) {
return new Node(val)
}
eq (n) {
return this.value === n.value
}
}
class BinarySearchTree {
constructor () {
this.root = null
}
inspect (currentNode = this.root, vals = []) {
if (!currentNode) return
vals.push(currentNode.value)
this.inspect(currentNode.left, vals)
this.inspect(currentNode.right, vals)
return vals
}
push (val) {
if (!this.root) {
this.root = Node.of(val)
return
}
let currentNode = this.root
const newNode = Node.of(val)
while (currentNode) {
if (val < currentNode.value) {
if (!currentNode.left) {
currentNode.left = newNode
break
} else {
currentNode = currentNode.left
}
} else {
if (!currentNode.right) {
currentNode.right = newNode
break
} else {
currentNode = currentNode.right
}
}
}
}
dfs (node, currentNode = this.root, path = []) {
if (!currentNode) return
path.push(currentNode.value)
if (currentNode.value === node.value) {
return path
}
if (node.value > currentNode.value) {
return this.dfs(node, currentNode.right, path)
} else {
return this.dfs(node, currentNode.left, path)
}
}
reverse (currentNode = this.root) {
if (!currentNode) return
const temp = currentNode.left
currentNode.left = currentNode.right
currentNode.right = temp
this.reverse(currentNode.left)
this.reverse(currentNode.right)
}
}
let bst = new BinarySearchTree()
bst.push(3)
bst.push(2)
bst.push(4)
bst.push(1)
bst.push(5)
console.log('depth-first search for 1', bst.dfs(Node.of(1)))
console.log('binary search tree', bst.inspect())
bst.reverse()
console.log('reversed binary search tree', bst.inspect())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment