Skip to content

Instantly share code, notes, and snippets.

@raaar
Last active June 21, 2021 08:21
Show Gist options
  • Save raaar/702a1421ca00666c7ccc5719e5e3152d to your computer and use it in GitHub Desktop.
Save raaar/702a1421ca00666c7ccc5719e5e3152d to your computer and use it in GitHub Desktop.
Binary search tree
class Node {
constructor(val) {
this.val = val;
this.left = undefined;
this.right = undefined;
this.parent = undefined;
}
}
class BST {
counstructor() {
this.head = undefined;
}
add(val) {
if (!this.head) {
this.head = new Node(val);
return this;
}
let current = this.head;
while (current) {
if (val === current.val) {
break;
}
let parent = current;
if (val < current.val) {
if (!current.left) {
current.left = new Node(val);
current.left.parent = parent;
break;
} else {
current = current.left;
}
}
if (val > current.val) {
if (!current.right) {
current.right = new Node(val);
current.right.parent = current;
} else {
current = current.right;
}
}
}
current = new Node(val);
}
BFS() {
let queue = [];
let data = [];
queue.push(this.head);
while (queue.length) {
let current = queue.shift();
data.push(current.val);
if (current.left) {
queue.push(current.left);
}
if (current.right) {
queue.push(queue.right);
}
}
return data;
}
}
let tree = new BST();
tree.add(5);
tree.add(4);
tree.add(2);
console.log(tree.BFS());
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment