Binary-search-tree In Javascript code #1326
Description
// Definition of TreeNode class
class TreeNode {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// Find a node in the tree with the given data
function find(root, data) {
if (!root) {
throw new Error("Error: Node with the given data doesn't exist.");
} else if (root.data === data) {
return root;
} else if (root.data < data) {
return find(root.right, data);
} else {
return find(root.left, data);
}
}
// Insert a new node with the given data into the tree
function insert(root, data) {
if (!root) {
return new TreeNode(data);
} else if (root.data === data) {
throw new Error("Error: Duplicate nodes are not allowed.");
} else if (root.data < data) {
root.right = insert(root.right, data);
} else {
root.left = insert(root.left, data);
}
return root;
}
// Check if the binary tree is full
function isFull(root) {
if (!root) {
return true;
}
if (!root.left && !root.right) {
return true;
}
if (root.left && root.right) {
return isFull(root.left) && isFull(root.right);
}
return false;
}
// Find the depth of the leftmost tree
function depth(root) {
let d = 0;
while (root !== null) {
root = root.left;
d++;
}
return d;
}
// Check if the binary tree is perfect using a recursive approach
function isPerfectRecursive(cur, depth, level = 0) {
if (!cur) {
return true;
}
if (!cur.left && !cur.right) {
return depth === level;
}
if (cur.left && cur.right) {
return isPerfectRecursive(cur.left, depth, level + 1) && isPerfectRecursive(cur.right, depth, level + 1);
}
return false;
}
// Count the number of nodes in the tree
function countNodes(cur) {
if (cur) {
return 1 + countNodes(cur.left) + countNodes(cur.right);
}
return 0;
}
// Find the height of the tree
function height(cur) {
if (cur) {
return 1 + Math.max(height(cur.left), height(cur.right));
}
return 0;
}
// Check if the binary tree is perfect
function isPerfect(root) {
const h = height(root) - 1;
const N = countNodes(root);
return N === Math.pow(2, h + 1) - 1;
}
// Check if the binary tree is perfect (alternate approach)
function isPerfectAlt(root) {
return isPerfectRecursive(root, depth(root) - 1);
}
// Print all leaf nodes in the binary tree
function leafNodes(root) {
if (!root) {
return;
}
if (!root.left && !root.right) {
process.stdout.write(root.data + ' ');
return;
}
if (root.left) {
leafNodes(root.left);
}
if (root.right) {
leafNodes(root.right);
}
}
// Find the minimum value node in the binary search tree
function findMin(root) {
if (!root) {
return null;
}
let p = root;
while (p.left !== null) {
p = p.left;
}
return p;
}
// Find the maximum value node in the binary search tree
function findMax(root) {
if (!root) {
return null;
}
let p = root;
while (p.right !== null) {
p = p.right;
}
return p;
}
// Delete a node with the given data from the binary search tree
function deleteNode(root, data) {
let m;
if (!root) {
console.log("NOT FOUND!!");
return root;
}
if (data < root.data) {
root.left = deleteNode(root.left, data);
return root;
}
if (data > root.data) {
root.right = deleteNode(root.right, data);
return root;
}
if (!root.left && !root.right) {
m = root;
delete m;
return null;
} else if (!root.left) {
m = root;
root = root.right;
delete m;
return root;
} else if (!root.right) {
m = root;
root = root.left;
delete m;
return root;
}
m = findMin(root.right);
root.data = m.data;
root.right = deleteNode(root.right, m.data);
return root;
}
// Print the tree in an inorder fashion
function print(root) {
if (root !== null) {
print(root.left);
process.stdout.write(root.data + ' ');
print(root.right);
}
}
// Free up the memory used by the tree
function free(root) {
if (root !== null) {
free(root.left);
free(root.right);
root = null;
}
}
// Main function
function main() {
let root = null;
root = insert(root, 37);
root = insert(root, 19);
root = insert(root, 4);
root = insert(root, 22);
root = insert(root, 51);
root = insert(root, 55);
root = insert(root, 42);
root = insert(root, 20);
root = insert(root, 11);
root = insert(root, 2);
print(root);
console.log();
let n = find(root, 19);
console.log("Value of n:", n.data);
if (isFull(root)) {
console.log("The binary tree is FULL");
} else {
console.log("The binary tree is not FULL");
}
if (isPerfect(root)) {
console.log("The binary tree is PERFECT");
} else {
console.log("The binary tree is not PERFECT");
}
console.log("Leaf nodes present in the binary tree are:");
leafNodes(root);
console.log();
n = findMax(root);
if (n) {
console.log("Maximum value present in the tree is:", n.data);
}
n = findMin(root);
if (n) {
console.log("Minimum value present in the tree is:", n.data);
}
root = deleteNode(root, 19);
console.log("Binary search tree after deletion:");
print(root);
console.log();
// Free up the memory used by the tree
free(root);
}
// Call the main function
main();