Search⌘ K
AI Features
Home
Courses
Mastering Data Structures and Sorting Algorithms in JavaScript

Deletion in Binary Search Tree

Explore how to remove nodes from a binary search tree in JavaScript by handling deletion of leaf nodes, nodes with one child, and nodes with two children, ensuring the structure remains valid.

We'll cover the following...

The function to remove a node from a binary search tree is as follows:

Node.js
remove(data) {
  this.root = this.removeNode(this.root, data)
}
removeNode(node, data) {
  if (!node) {
    return null;
  }
  if (data < node.data) {
    node.left = this.removeNode(node.left, data);
    return node;
  } else if (data > node.data) {
    node.right = this.removeNode(node.right, data);
    return node;
  } else {
    if (!node.left && !node.right) {
      node = null;
      return node;
    }
    if (!node.left) {
      node = node.right;
      return node;
    } 
    if (!node.right) {
      node = node.left;
      return node;
    }
    
    let min = this.findMinNode(node.right);
    node.data = min.data;
    node.right = this.removeNode(node.right, min.data);
    return node;
  }
}

Removing a leaf

First, we invoke the remove function. We set the root’s value equal to whatever gets returned from the removeNode function. We pass two arguments to this function: the root, and the node’s value that we want to delete, 9 in this case.

Inside the removeNode function, we get to the first if-statement. Nodes are present in the tree, so !node returns false. We get to the second if-statement, which returns true as data (9) is smaller than node.data (27). Now, we set the left node’s value equal to whatever gets returned from the removeNode function, which we invoke again, only now with the value of the left node (10) as the first argument.

Again, we get to the first if-statement, which returns false. The second if-statement returns true again, as data (9) is smaller than node.data (10). Again, we set the left node’s value equal to whatever gets returned from the removeNode ...