Last active
January 4, 2017 23:48
-
-
Save ivtpz/ba650be6e5d262d61d7d17bef89b764c to your computer and use it in GitHub Desktop.
Start of a JavaScript Binary Search Tree
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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