Skip to content

Instantly share code, notes, and snippets.

@akhrszk
Last active December 11, 2021 12:53
Show Gist options
  • Save akhrszk/537b19c384db3ce141dcbb547a2cfb4c to your computer and use it in GitHub Desktop.
Save akhrszk/537b19c384db3ce141dcbb547a2cfb4c to your computer and use it in GitHub Desktop.
Binary Search Tree in JavaScript
class Node {
constructor(value) {
this.value = value
this.left = undefined
this.right = undefined
}
}
Node.prototype.setLeft = function (node) {
this.left = node
}
Node.prototype.setRigth = function (node) {
this.right = node
}
Node.prototype.unsetLeft = function () {
this.left = undefined
}
Node.prototype.unsetRigth = function () {
this.right = undefined
}
Node.prototype.min = function () {
return this.left ? this.left.min() : this
}
Node.prototype.max = function () {
return this.right ? this.right.max() : this
}
Node.prototype.insert = function (node) {
if (this.value < node.value) {
this.right ? this.right.insert(node) : this.setRigth(node)
} else if (this.value > node.value) {
this.left ? this.left.insert(node) : this.setLeft(node)
} else {
console.log(`value:${node.value} is already exists`)
}
}
Node.prototype.find = function (value) {
if (this.value < value) {
return this.right && this.right.find(value)
} else if (this.value > value) {
return this.left && this.left.find(value)
} else {
return this
}
}
Node.prototype.remove = function (value) {
if (this.left && this.left.value === value) {
if (this.left.left && this.left.right) {
const replacement = this.left.left.max()
this.left.remove(replacement.value)
this.setLeft(replacement)
} else if (this.left.left) {
this.setLeft(this.left.left)
} else if (this.left.right) {
this.setLeft(this.left.right)
} else {
this.unsetLeft()
}
} else if (this.right && this.right.value === value) {
if (this.right.left && this.right.right) {
const replacement = this.right.left.max()
this.right.remove(replacement.value)
this.setRigth(replacement)
} else if (this.right.left) {
this.setRigth(this.right.left)
} else if (this.right.right) {
this.setRigth(this.right.right)
} else {
this.unsetRigth()
}
} else {
this.left && this.left.remove(value)
this.right && this.right.remove(value)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment