Suggestion for Data Structures: Delete a Node with Two Children in a Binary Search Tree

Challenge: Delete a Node with Two Children in a Binary Search Tree

Hint 1: This challenge works best when combining what you’ve learned in the lesson on finding the min and max values in a binary tree with the code from the previous lessons on removing elements from a binary tree.

Hint 2: Once you find the minimum value for the right side tree, you recursively remove the node with that value from the tree, then replace the value of the target node with the minimum value you found.

Solution
var displayTree = tree => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

function BinarySearchTree() {
  this.root = null;

  this.remove = function(value) {
    if (this.root === null) {
      return null;
    }
    var target;
    var parent = null;
    // Find the target value and its parent
    (function findValue(node = this.root) {
      if (value == node.value) {
        target = node;
      } else if (value < node.value && node.left !== null) {
        parent = node;
        return findValue(node.left);
      } else if (value < node.value && node.left === null) {
        return null;
      } else if (value > node.value && node.right !== null) {
        parent = node;
        return findValue(node.right);
      } else {
        return null;
      }
    }.bind(this)());
    if (target === null) {
      return null;
    }
    // Count the children of the target to delete
    var children =
      (target.left !== null ? 1 : 0) + (target.right !== null ? 1 : 0);
    // Case 1: Target has no children
    if (children === 0) {
      if (target == this.root) {
        this.root = null;
      } else {
        if (parent.left == target) {
          parent.left = null;
        } else {
          parent.right = null;
        }
      }
    }
    // Case 2: Target has one child
    else if (children == 1) {
      var newChild = target.left !== null ? target.left : target.right;
      if (parent === null) {
        target.value = newChild.value;
        target.left = null;
        target.right = null;
      } else if (newChild.value < parent.value) {
        parent.left = newChild;
      } else {
        parent.right = newChild;
      }
      target = null;
    }
    // Only change code below this line
    // Case 3: Target has two children
    else if (children === 2) {
      // find the smallest value from the right side
      const newChildValue = this.findMin(target.right);
      // recursively remove the node with this value
      this.remove(newChildValue);
      // set the target value to the new child value
      target.value = newChildValue;
    }
  };

  // Find the minimum and maximum values from a tree or subtree
  this.findMin = (root = this.root) => {
    if (!this.root) return null;
    return root.left ? this.findMin(root.left) : root.value;
  }
  this.findMax = (root = this.root) => {
    if (!this.root) return null;
    return root.right ? this.findMax(root.right) : root.value;
  }
}

Link to the challenge:

Thank you for your guide post contribution. I have taken your suggestions and included them in the guide post.

We look forward to your further contribution.

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.