Skip to content

Instantly share code, notes, and snippets.

@josh-stevens
Created February 10, 2019 04:41
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save josh-stevens/c6159bf7a170fb10a761eb1b46264138 to your computer and use it in GitHub Desktop.
Save josh-stevens/c6159bf7a170fb10a761eb1b46264138 to your computer and use it in GitHub Desktop.
Basic Binary Search Tree in Javascript
class Node {
constructor(value, parent) {
this.value = value;
this.parent = parent || null;
this.left = null;
this.right = null;
}
insert(value) {
if (value > this.value) {
if (this.right === null) {
this.right = new Node(value, this);
return;
} else {
this.right.insert(value);
return;
}
} else {
if (this.left === null) {
this.left = new Node(value, this);
return;
} else {
this.left.insert(value);
return;
}
}
}
remove(value) {
if (value === this.value) {
if (this.left === null && this.right === null) {
if (this.parent.left.value === value) {
this.parent.left = null;
} else {
this.parent.right = null;
}
return;
} else {
if (this.left === null && this.right !== null) {
if (this.parent.left.value === value) {
this.parent.left = this.right;
} else {
this.parent.right = this.right;
}
this.right.parent = this.parent;
} else if (this.right === null && this.left !== null) {
if (this.parent.left.value === value) {
this.parent.left = this.left;
} else {
this.parent.right = this.left;
}
this.left.parent = this.parent;
} else {
const s = this.successor();
this.value = s.value;
this.right.remove(s.value);
}
}
}
if (value > this.value && this.right !== null) {
this.right.remove(value);
return;
}
if (value < this.value && this.left !== null) {
this.left.remove(value);
return;
}
}
search(value) {
if (value === this.value) {
return this;
}
if (value > this.value && this.right !== null) {
return this.right.search(value);
}
if (value < this.value && this.left !== null) {
return this.left.search(value);
}
return null;
}
findMin() {
if (this.left === null) return this;
return this.left.findMin();
}
findMax() {
if (this.right === null) return this;
return this.right.findMax();
}
predecessor(value = this.value) {
const valueNode = this.search(value);
if (valueNode === null) return null;
if (valueNode.left !== null) {
return valueNode.left.findMax();
}
let p = valueNode.parent,
t = valueNode;
while (p !== null && t == p.left) {
t = p;
p = t.parent;
}
if (p === null) return -1;
return p;
}
successor(value = this.value) {
const valueNode = this.search(value);
if (valueNode === null) return null;
if (valueNode.right !== null) {
return valueNode.right.findMin();
}
let p = valueNode.parent,
t = valueNode;
while (p !== null && t == p.right) {
t = p;
p = t.parent;
}
if (p === null) return -1;
return p;
}
inOrderTraversal() {
if (this.left) {
this.left.inOrderTraversal();
}
console.log(this.value);
if (this.right) {
this.right.inOrderTraversal();
}
}
getHeight() {
const leftHeight = this.left === null ? -1 : this.left.getHeight();
const rightHeight = this.right === null ? -1 : this.right.getHeight();
return Math.max(leftHeight, rightHeight) + 1;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment