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

Delete a Node with Two Children in a Binary Search Tree


Hints

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.


Solutions

Solution 1 (Click to Show/Hide)
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;
  // Only change code below this line
  this.remove = function(value) {
    if (!this.root) return null;

    // find the node
    let parent;
    let target = this.root;
    while (target && target.value !== value) {
      parent = target;
      if (target.value > value) {
        target = target.left;
      } else {
        target = target.right;
      }
    }
    if (!target) return null;

    // remove the node
    // -- zero or one children
    if (!(target.left && target.right)) {
      // ---- root node
      const replacement = target.right ? target.right : target.left;
      if (!parent) {
        this.root = replacement;
      } else {
        // ---- other node
        const direction = parent.left === target ? "left" : "right";
        parent[direction] = replacement;
      }
    } else {
      // -- two children
      // ---- replace current value with smallest child
      const newChildValue = this.findMin(target.right);
      this.remove(newChildValue);
      target.value = newChildValue;
    }
  }

  this.findMin = function(node = this.root) {
    if (!node) return null;
    return node.left ? this.findMin(node.left) : node.value;
  }

  this.findMax = function(node = this.root) {
    if (!node) return null;
    return node.right ? this.findMax(node.right) : node.value;
  }
}
3 Likes