Binary-search-tree In Javascript code

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

MakeContributions / DSA

Binary-search-tree In Javascript code #1326