BST_Traversal
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273
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;
}
JavaScript
INFO