|
A Binary Search Tree (BST) is a type of binary tree where each node has at most two children referred to as the left child and the right child. The value of the left child node is less than the value of the current node and the value of the right child node is greater than the value of the current node in the binary search tree. We will insert nodes first before deleting nodes.
There are several approaches to deleting all nodes of a binary search tree using JavaScript which are as follows:
Using Node Traversal If the tree root is null, return immediately. Otherwise, initialize a stack and a set to keep track of visited nodes. Use a stack to simulate the recursive call stack. Push the root node onto the stack. Check if the current node has left and right children that haven’t been visited yet. Push children onto the stack if they exist and haven’t been visited. If both children are visited or non-existent, pop the node from the stack, mark it as visited, and set its children to null. After all nodes are processed, set the root to null to complete the deletion of the BST.
Example: To demonstrate deleting all nodes of a binary search tree Using Iterative Traversal of nodes.
JavaScript
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new TreeNode(value);
if (this.root === null) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode);
}
}
insertNode(node, newNode) {
if (newNode.value < node.value) {
if (node.left === null) {
node.left = newNode;
} else {
this.insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
this.insertNode(node.right, newNode);
}
}
}
deleteTreeIteratively() {
if (this.root === null) return;
const stack = [];
const visited = new Set();
stack.push(this.root);
while (stack.length > 0) {
const current = stack[stack.length - 1];
if (current.left && !visited.has(current.left)) {
stack.push(current.left);
} else if (current.right && !visited.has(current.right)) {
stack.push(current.right);
} else {
stack.pop();
visited.add(current);
console.log(`Deleting node with value: ${current.value}`);
current.left = null;
current.right = null;
}
}
this.root = null;
}
deleteAllNodes() {
this.deleteTreeIteratively();
}
}
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(20);
bst.insert(3);
bst.insert(7);
bst.deleteAllNodes();
console.log("All nodes deleted");
OutputDeleting node with value: 3
Deleting node with value: 7
Deleting node with value: 5
Deleting node with value: 20
Deleting node with value: 10
All nodes deleted
Time Complexity: O(n)
Space Complexity: O(h)
Using RecursionIf the node is null, return immediately. This serves as the base case for the recursion. Recursively call the deleteTree method on the left child of the current node. Recursively call the deleteTree method on the right child of the current node. Print a message indicating that the current node is being deleted. Set the left and right pointers of the current node to null, effectively deleting it. After all nodes are processed and deleted, set the root of the tree to null to complete the deletion of the BST.
Example: To demonstrate deleting all nodes of a binary search tree Using Recursive Post-order Traversal.
JavaScript
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new TreeNode(value);
if (this.root === null) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode);
}
}
insertNode(node, newNode) {
if (newNode.value < node.value) {
if (node.left === null) {
node.left = newNode;
} else {
this.insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
this.insertNode(node.right, newNode);
}
}
}
deleteTree(node) {
if (node === null) return;
// Recur on left subtree
this.deleteTree(node.left);
// Recur on right subtree
this.deleteTree(node.right);
// Delete current node
console.log(`Deleting node with value: ${node.value}`);
node.left = null;
node.right = null;
}
deleteAllNodes() {
this.deleteTree(this.root);
this.root = null;
}
}
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(20);
bst.insert(3);
bst.insert(7);
bst.deleteAllNodes();
console.log("All nodes deleted");
OutputDeleting node with value: 3
Deleting node with value: 7
Deleting node with value: 5
Deleting node with value: 20
Deleting node with value: 10
All nodes deleted
Time Complexity: O(n)
Space Complexity: O(h)
Using Morris TraversalMorris Traversal is a method to traverse a binary tree with O(1) space complexity. This method modifies the tree during the traversal but ensures it is restored to its original structure once traversal is complete. We can leverage this method to delete all nodes of a binary search tree in an efficient manner.
Example: The Morris Traversal method works by creating temporary links between nodes to traverse the tree without using a stack or recursion. After processing the nodes, the tree structure is restored.
JavaScript
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function deleteBST(root) {
let current = root;
while (current !== null) {
if (current.left === null) {
// Process current node
console.log("Deleting node with value:", current.value);
current.value = null;
current = current.right;
} else {
// Find the inorder predecessor of current
let predecessor = current.left;
while (predecessor.right !== null && predecessor.right !== current) {
predecessor = predecessor.right;
}
if (predecessor.right === null) {
// Make current the right child of its inorder predecessor
predecessor.right = current;
current = current.left;
} else {
// Restore the tree and process current
predecessor.right = null;
console.log("Deleting node with value:", current.value);
current.value = null;
current = current.right;
}
}
}
// Set root to null to complete the deletion
root = null;
}
// Example usage
let root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(6);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);
root.right.left = new TreeNode(5);
root.right.right = new TreeNode(7);
console.log(deleteBST(root));
OutputDeleting node with value: 1
Deleting node with value: 2
Deleting node with value: 3
Deleting node with value: 4
Deleting node with value: 5
Deleting node with value: 6
Deleting node with value: 7
unde...
|
.png){kind=small}
.png){kind=small}
