Skip to content

Instantly share code, notes, and snippets.

@ivtpz
Last active January 4, 2017 23:48
Show Gist options
  • Save ivtpz/ba650be6e5d262d61d7d17bef89b764c to your computer and use it in GitHub Desktop.
Save ivtpz/ba650be6e5d262d61d7d17bef89b764c to your computer and use it in GitHub Desktop.
Start of a JavaScript Binary Search Tree
class BST {
constructor(value) {
this.root = new Node(value);
}
insert(value) {
var recurse = function(node) {
if (value < node.value) {
node.left ? recurse(node.left) : node.left = new Node(value);
} else {
node.right ? recurse(node.right) : node.right = new Node(value);
}
}
recurse(this.root)
}
contains(value) {
var recurse = function(node) {
if (node === null) {
return false;
}
if (node.value === value) {
return node;
}
if(value > node.value) {
return recurse(node.right);
} else if (value < node.value) {
return recurse(node.left);
}
}
return recurse(this.root);
}
_remove(value) {
var recurse = function(node) {
if (node === null) {
return false;
}
if (node.value === value) {
node = null;
return true;
}
if(value > node.value) {
return recurse(node.right);
} else if (value < node.value) {
return recurse(node.left);
}
}
return recurse(this.root);
}
delete(value) {
let nodeToDelete = this.contains(value);
var parent
if (!nodeToDelete) {
return false;
}
//if no children
if (!nodeToDelete.left && !nodeToDelete.right) {
this._remove(nodeToDelete.value)
} else if (nodeToDelete.left && nodeToDelete.right) {
// find value of successor
// go right, then go left untill no left child
function rightThenLeft(node) {
var current = node.right;
while (current.left) {
current = current.left;
}
return current;
}
var replacement = rightThenLeft(node)
// set value of node to delete to successor
// delete successor node
} else {
//1 kiddo
}
}
}
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
4
0 5 --> change right child
-1 3 ?10
1 3.5 6 12
11 13
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment