Created
September 26, 2017 04:47
-
-
Save christopherhill/28d3848007b2d4543b3f13971a9ffb3a to your computer and use it in GitHub Desktop.
This file contains 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 Node { | |
constructor(val) { | |
this.val = val; | |
this.left = null; | |
this.right = null; | |
} | |
} | |
class BinarySearchTree { | |
constructor() { | |
this.root = null; | |
} | |
find(val) { | |
const root = this.root; | |
if (!root) return false; | |
let result = null; | |
function recurse(curNode) { | |
if (curNode.val === val) { | |
result = curNode; | |
} | |
if (curNode.left) { | |
recurse(curNode.left); | |
} | |
if (curNode.right) { | |
recurse(curNode.right); | |
} | |
} | |
recurse(root); | |
return result; | |
} | |
push(val) { | |
let root = this.root; | |
let newNode = new Node(val); | |
if (!root) { | |
this.root = newNode; | |
return; | |
} | |
// there is a root, lookup | |
let curNode = root; | |
while (curNode) { | |
if (val < curNode.val) { // goes on the left | |
if (!curNode.left) { | |
curNode.left = newNode; | |
break; | |
} else { | |
curNode = curNode.left; | |
} | |
} else if (val > curNode.val) { | |
if (!curNode.right) { | |
curNode.right = newNode; | |
break; | |
} else { | |
curNode = curNode.right; | |
} | |
} | |
} | |
} | |
size() { | |
const root = this.root; | |
if (!root) return 0; | |
let size = 1; | |
function recurse(curNode) { | |
if (curNode.left) { | |
console.log('left') | |
size += 1; | |
recurse(curNode.left); | |
} | |
if (curNode.right) { | |
console.log('right'); | |
size += 1; | |
recurse(curNode.right); | |
} | |
} | |
recurse(root); | |
return size; | |
} | |
maxDepth() { | |
const root = this.root; | |
if (!root) return 0; | |
let curNode = root; | |
function recurse(curNode) { | |
if (curNode === null) return 0; | |
let leftDepth = recurse(curNode.left); | |
let rightDepth = recurse(curNode.right); | |
return Math.max(leftDepth, rightDepth) + 1; | |
} | |
let result = recurse(root); | |
return result; | |
} | |
minValue() { | |
const root = this.root; | |
if (!root) return 0; | |
let curNode = root; | |
while (curNode) { | |
if (curNode.left) { | |
curNode = curNode.left; | |
} else break; | |
} | |
return curNode.val; | |
} | |
maxValue() { | |
const root = this.root; | |
if (!root) return 0; | |
let curNode = root; | |
while (curNode) { | |
if (curNode.right) { | |
curNode = curNode.right; | |
} else break; | |
} | |
return curNode.val; | |
} | |
} | |
let b = new BinarySearchTree(); | |
b.push(3); | |
b.push(2); | |
b.push(5); | |
b.push(7); | |
b.push(4); | |
b.push(6); | |
b.push(9); | |
console.log(b.root); | |
console.log(b.size()) | |
console.log(b.find(9)); | |
console.log(b.maxDepth()); | |
console.log(b.minValue()); | |
console.log(b.maxValue()); | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment