Skip to content
This repository has been archived by the owner on May 29, 2024. It is now read-only.

Binary-search-tree In Javascript code #1326

Open
Ankitmohanty2 opened this issue Apr 5, 2024 · 1 comment
Open

Binary-search-tree In Javascript code #1326

Ankitmohanty2 opened this issue Apr 5, 2024 · 1 comment

Comments

@Ankitmohanty2
Copy link

// 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();

Copy link

welcome bot commented Apr 5, 2024

Thanks for opening your first issue here! Be sure to follow the issue template!

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant