class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BST {
constructor() {
this.root = null;
}
lookup(value) {
return this._findValue(this.root, value);
}
insert(value) {
const newNode = new Node(value);
if(this.root === null) {
this.root = newNode;
}
else {
this._createNewLeaf(this.root, newNode);
}
}
traverse(node) {
const tree = { value: node.value };
tree.left = node.left === null ? null : traverse(node.left);
tree.right = node.right === null ? null : traverse(node.right);
return tree;
}
remove(value) {
const node = this.lookup(value)
if(!node) {
return false;
}
const parent = this._findParent(this.root, node.value)
//check if node has no children
if(node.left === null && node.right === null) {
if(value < parent.value) {
parent.left = null;
}
else {
parent.right = null;
}
}
//check if node has 1 child and its to the right
else if(!node.left) {
//check if root
if(node == parent) {
this.root = node.right;
return;
}
if(value < parent.value) {
parent.left = node.right;
}
else {
parent.right = node.right;
}
}
//check if node has 1 child and its to the left
else if(!node.right) {
//check if root
if(node == parent) {
this.root = node.left;
return;
}
if(value < parent.value) {
parent.left = node.left;
}
else {
parent.right = node.left;
}
}
//node has two children
else {
const successor = this.findMin(node.right);
const successorParent = this._findParent(parent, successor.value);
if(successor.right) {
successorParent.left = successor.right;
}
else {
successorParent.left = null;
}
successor.left = node.left;
successor.right = node.right;
//check if root
if(node == parent) {
this.root = successor;
return;
}
if(value < parent.value) {
parent.left = successor;
}
else {
parent.right = succ0essor;
}
}
}
findMin(node) {
let currentNode = node;
while(currentNode.left !== null) {
currentNode = currentNode.left;
}
return currentNode;
}
BFS() {
let list = [];
let queue = [];
queue.push(this.root);
while(queue.length > 0) {
let currentNode = queue.shift();
list.push(currentNode.value);
if(currentNode.left) {
queue.push(currentNode.left);
}
if(currentNode.right) {
queue.push(currentNode.right);
}
}
return list;
}
BFSr(queue, list) {
if (!queue.length) {
return list;
}
let currentNode = queue.shift();
list.push(currentNode.value);
if(currentNode.left) {
queue.push(currentNode.left);
}
if(currentNode.right) {
queue.push(currentNode.right);
}
return this.BFSr(queue, list);
}
inOrder() {
return this.traverseInOrder(this.root, []);
}
preOrder() {
return this.traversePreOrder(this.root, []);
}
postOrder() {
return this.traversePostOrder(this.root, []);
}
traverseInOrder(node, list) {
if(node.left) {
this.traverseInOrder(node.left, list);
}
list.push(node.value);
if(node.right) {
this.traverseInOrder(node.right, list);
}
return list;
}
traversePreOrder(node, list) {
list.push(node.value);
if(node.left) {
this.traversePreOrder(node.left, list);
}
if(node.right) {
this.traversePreOrder(node.right, list);
}
return list;
}
traversePostOrder(node, list) {
if(node.left) {
this.traversePostOrder(node.left, list);
}
if(node.right) {
this.traversePostOrder(node.right, list);
}
list.push(node.value);
return list;
}
_findParent(node, value) {
if(value == node.value) {
//root node
return node;
}
if(value > node.value) {
if(value == node.right.value) {
return node;
}
return this._findParent(node.right, value);
}
else {
if(value == node.left.value) {
return node;
}
return this._findParent(node.left, value);
}
}
_createNewLeaf(node, newNode) {
if(newNode.value > node.value) {
if(node.right !== null) {
this._createNewLeaf(node.right, newNode);
}
else {
node.right = newNode;
}
}
else {
if(node.left !== null) {
this._createNewLeaf(node.left, newNode);
}
else {
node.left = newNode;
}
}
}
_findValue(node, value) {
if(node === null || value == node.value) {
return node;
}
if(value > node.value) {
return this._findValue(node.right, value);
}
else {
return this._findValue(node.left, value);
}
}
}
const bst = new BST();
bst.insert(9);
bst.insert(4);
bst.insert(6);
bst.insert(20);
bst.insert(170);
bst.insert(15);
bst.insert(1);
//console.log(bst.lookup(6));
//console.log(JSON.stringify(traverse(bst.root)));
//console.log(bst.BFSr([bst.root], []));
console.log(bst.inOrder());
console.log(bst.preOrder());
console.log(bst.postOrder());
console.log(bst);
//console.log(JSON.stringify(traverse(bst.root)));
function traverse(node) {
const tree = { value: node.value };
tree.left = node.left === null ? null : traverse(node.left);
tree.right = node.right === null ? null : traverse(node.right);
return tree;
}
