Check if BST
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
let node = new Node(value);
if (this.root === null) {
this.root = node;
return this;
}
let curr = this.root;
while(curr !== null) {
if (value > curr.value) {
if (curr.right) {
curr = curr.right;
} else {
curr.right = node;
return;
}
} else {
if (curr.left) {
curr = curr.left;
} else {
curr.left = node;
return;
}
}
}
}
lookup(value) {
if (this.root === null) {
return null;
}
let curr = this.root;
while (curr !== null ) {
if (value > curr.value) { // go right
if (curr.right) {
curr = curr.right;
} else {
return null;
}
} else if( value < curr.value) { // go left, ie value is less than curr.value
if (curr.left) {
curr = curr.left;
} else {
return null;
}
} else { // if value == curr.value
return curr;
}
}
}
remove(value) {
if (this.root === null) {
return null;
}
let parent = this.root;
let curr = this.root;
let left = this.root.left;
let right = this.root.right;
while (curr !== null ) {
console.log(curr.value);
if (value > curr.value) {
console.log("going right");
parent = curr;
curr = curr.right;
left = curr.left;
right = curr.right;
} else if (value < curr.value) {
console.log("going left");
parent = curr;
curr = curr.left
left = curr.left;
right = curr.right;
} else if (curr.value === value) {
if (curr.left === null && curr.right === null) { // leaf node
if (value < parent.value) {
parent.left = null;
} else {
parent.right = null;
}
return curr;
}
if (curr.right.left === null && curr.right.right === null) {
parent.right = curr.right;
parent.right.left = left;
return curr;
}
if (curr.right.left === null && curr.right.right !== null) {
parent.right = curr.right;
parent.right.left = left;
return curr;
}
if (curr.right.left !== null && curr.right.right === null) {
parent.right = curr.right.left;
parent.right.right = curr.right;
parent.right.left = curr.left;
curr.right.left = null;
}
curr = null;
}
}
}
preorderTraversal(node, list) {
list.push(node.value);
if (node.left !== null) {
this.preorderTraversal(node.left, list);
}
if (node.right !== null) {
this.preorderTraversal(node.right, list);
}
return list;
}
postorderTraversal(node, list) {
if (node.left !== null) {
this.postorderTraversal(node.left, list);
}
if (node.right !== null) {
this.postorderTraversal(node.right, list);
}
list.push(node.value);
return list;
}
inorderTraversal(node, list) {
if (node.left !== null) {
this.inorderTraversal(node.left, list);
}
list.push(node.value);
if (node.right !== null) {
this.inorderTraversal(node.right, list);
}
return list;
}
}
// Helper function to check if a tree is BST
// within a given range
function isBSTUtil(node, min, max) {
if (node === null) return true;
// If the current node's data
// is not in the valid range, return false
if (node.data < min || node.data > max) return false;
// Recursively check the left and
// right subtrees with updated ranges
return isBSTUtil(node.left, min, node.data - 1) &&
isBSTUtil(node.right, node.data + 1, max);
}
// Function to check if the entire binary tree is a BST
function isBST(root) {
return isBSTUtil(root, -Infinity, Infinity);
}
const tree = new BinarySearchTree();
tree.insert(9);
tree.insert(4);
tree.insert(20);
tree.insert(1);
tree.insert(6);
tree.insert(15);
tree.insert(170);
// tree.insert(180);
// tree.insert(179);
// tree.insert(181);
// tree.insert(150);
// console.log(tree.remove(20));
if (isBST(tree.root)) {
console.log("True");
} else {
console.log("False");
}
JavaScript
INFO