Skip to content

Instantly share code, notes, and snippets.

@ziyoshams
Last active August 3, 2018 20:35
Show Gist options
  • Save ziyoshams/61892fce9e3afd62f7af8d19f5dee897 to your computer and use it in GitHub Desktop.
Save ziyoshams/61892fce9e3afd62f7af8d19f5dee897 to your computer and use it in GitHub Desktop.
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BST {
constructor(value) {
this.root = null;
}
insert(value) {
if (!this.root) {
this.root = new Node(value);
} else {
// inserts recursively.
this.insertHelper(this.root, value);
}
}
// helper function to insert recursively.
insertHelper(node, value) {
if (value < node.value && node.left === null) {
node.left = new Node(value);
} else if (value >= node.value && node.right === null) {
node.right = new Node(value);
} else {
if (value < node.value) {
this.insertHelper(node.left, value);
} else {
this.insertHelper(node.right, value);
}
}
}
// Breadth First Search
bfs() {
console.log('\nprinting BFS');
let q = [];
let output = [];
q.push(this.root);
while (q.length) {
let node = q.pop();
output.push(node.value);
if (node.left) q.unshift(node.left);
if (node.right) q.unshift(node.right);
}
console.log(output);
}
// Depth First Search
// If traversal type is not passed as a parameter (e.g in-order, pre-order, post-order),
/// it defaults to 'in-order' traversal.
dfs(traversalType) {
let output = [];
if (this.root) {
if (traversalType === 'post-order') {
console.log('\nprinting DFS post-order');
this.dfsHelperPostOrder(this.root, output);
} else if (traversalType === 'pre-order') {
console.log('\nprinting DFS pre-order');
this.dfsHelperPreOrder(this.root, output);
} else {
console.log('\nprinting DFS in-order');
this.dfsHelperInOrder(this.root, output);
}
}
console.log(output);
}
dfsHelperInOrder(node, output) {
if (node.left) this.dfsHelperInOrder(node.left, output);
output.push(node.value);
if (node.right) this.dfsHelperInOrder(node.right, output);
}
dfsHelperPreOrder(node, output) {
output.push(node.value);
if (node.left) this.dfsHelperPreOrder(node.left, output);
if (node.right) this.dfsHelperPreOrder(node.right, output);
}
dfsHelperPostOrder(node, output) {
if (node.left) this.dfsHelperPostOrder(node.left, output);
if (node.right) this.dfsHelperPostOrder(node.right, output);
output.push(node.value);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment