Question 225988 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Understanding parent nodes when removing node from BST

I am trying to remove a node from a BST and I actually got the code to work but there is one part of it I do not understand. This is my code:

class BST {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }

  remove(value, parentNode = null) {
    let currentNode = this;
    while (currentNode !== null) {
      if (value < currentNode.value) {
        parentNode = currentNode;
        currentNode = currentNode.left;
      } else if (value > currentNode.value) {
        parentNode = currentNode;
        currentNode = currentNode.right;
      } else {
        if (currentNode.left !== null && currentNode.right !== null) {
          currentNode.value = currentNode.right.getMinValue();
          currentNode.right.remove(currentNode.value, currentNode);
        } else if (parentNode === null) {
          if (currentNode.left !== null) {
            currentNode.value = currentNode.left.value;
            currentNode.right = currentNode.left.right;
            currentNode.left = currentNode.left.left;
          } else if (currentNode.right !== null) {
            currentNode.value = currentNode.right.value;
            currentNode.left = currentNode.right.left;
            currentNode.right = currentNode.right.right;
          }
        } else if (parentNode.left === currentNode) {
          parentNode.left = currentNode.left !== null ? currentNode.left : currentNode.right;
        } else if (parentNode.right === currentNode) {
          parentNode.right = currentNode.left !== null ? currentNode.left : currentNode.right;
        }
        break;
      }
    }
    return this;
  }

  getMinValue() {
    let currentNode = this;
    while (currentNode.left !== null) {
      currentNode = currentNode.left;
    }
    return currentNode.value;
  }
}

I use the getMinValue method for the edge case where I have to remove a node with two children nodes. I use that method to replace the current node’s value (the one that I’m removing) with the lowest value from the right subtree of that node. I then call the remove method to remove that same node from the right subtree.

What I don’t understand is the following line:

currentNode.right.remove(currentNode.value, currentNode);

I know that this line is removing the node that was used as a replacement for the base node but I don’t understand why I have to pass the currentNode as the parentNode argument.
Won’t the remove method have to find the node that needs to be removed first and hence change the parentNode value anyways? Why can’t I just make that argument null?

Tags:

2

Answers


  1. 0

    This algorithm keeps track of parentNode as it descends through the tree so that it can set the parentNode.left or parentNode.right property to null whenever currentNode turns out to be the node to be removed.

    Now when you call remove again in the case you describe, you also need to pass on a reference for parentNode, as it might be that this currentNode.right is a node without left child, and thus is the one that needs to be removed. For that removal to happen, its parent node needs its right property to be set to null, and so a reference to it is needed.

    If you would pass null for that parameter it would work fine in cases where currentNode.right has a left child — you would descend further down and so set parentNode appropriately. But for the case where it doesn’t have a left child, it is that node that needs to be removed, and so we need to know its parent.

    Login or Signup to reply.
  2. 0

    parentNode is needed when the node being removed is the root of the subtree. In this case, the appropriate child link in the parent has to be updated to point to the corresponding child of the node being removed.

    When parentNode === null, it means you’re removing the top-most node in the entire BST, so there’s no parent to update. You can’t use that code path when you’re removing a node in the middle of the tree.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search