BST Traversal
class BinarySearchTree {
constructor() {
this.root = null;
}
insertNode(val) {
const node = {
data: val,
left: null,
right: null,
}
let currentNode;
if (!this.root) {
this.root = node;
} else {
currentNode = this.root;
while(currentNode) {
if (val < currentNode.data) {
if (!currentNode.left) {
currentNode.left = node;
break;
} else {
currentNode = currentNode.left;
}
} else if (val > currentNode.data) {
if (!currentNode.right) {
currentNode.right = node;
break;
} else {
currentNode = currentNode.right;
}
} else {
console.log('IGNORE')
break;
}
}
}
}
preOrderTraversal(root) {
console.log(root.data);
if (root.left) {
this.preOrderTraversal(root.left);
}
if (root.right) {
this.preOrderTraversal(root.right);
}
}
inOrderTraversal(root) {
if (root.left) {
this.inOrderTraversal(root.left);
}
console.log(root.data);
if (root.right) {
this.inOrderTraversal(root.right);
}
}
postOrderTraversal(root) {
if (root.left) {
this.postOrderTraversal(root.left);
}
if (root.right) {
this.postOrderTraversal(root.right);
}
console.log(root.data);
}
breadFirstSearch(bst) {
let temp;
const queue = [];
queue.push(bst.root);
while(queue.length) {
temp = queue.splice(0, 1)[0];
console.log(temp.data);
if (temp.left) queue.push(temp.left);
if (temp.right) queue.push(temp.right);
}
}
}
const BST = new BinarySearchTree();
BST.insertNode(5);
BST.insertNode(4);
BST.insertNode(3);
BST.insertNode(2);
BST.insertNode(6);
BST.insertNode(9);
BST.insertNode(8);
BST.insertNode(10);
// console.log(JSON.stringify(BST, null, 2))
console.log('DEPTH FIRST SEARCH')
// BST.preOrderTraversal(BST.root);
BST.inOrderTraversal(BST.root);
// BST.postOrderTraversal(BST.root);
console.log('BREADTH FIRST SEARCH');
BST.breadFirstSearch(BST)
no comments
sign in to comment