Binary Search Tree - remove function not changing the original tree

user_12204573 0
Viewed 43

I am trying to remove a root node in a binary search tree.

bst.remove(1) gives the correct output but it doesn't change the tree itself.

So if I check bst after calling bst.remove(1) the output is different. Why is it the case?

If I run bst=bst.left||bst.right;, I get the correct output, which leads me to believe that my function isn't changing the original tree in place.

remove(key) {
   return this.removeImpl(key, this);
  }

  removeImpl(key, node){  
    
      if (node != null) {
      if (key < node.value) {
        // Key might be in the left subtree.
        node.left = this.removeImpl(key, node.left);
      } else if (key > node.value) {
        node.right = this.removeImpl(key, node.right);
      } else {
        // Node found. 
        // Let's see if it has two children.
        
        
        if (node.left && node.right) {
          // Replace current node with 
          // predecessor data
          
          node.value = this.minimum(node.right);
          node.right = this.removeImpl(node.value, node.right);
        } else {
          // Only 1 child.
          // Let's return the child that's valid.
          
          node = node.left || node.right; //node to be removed becomes it's right or left child
    
        }
      }
    }
    return node;
  }

var bst=new BST(1);
bst.insert(2);
bst.insert(3);
bst.insert(4);

bst.remove(1);
binary-search-tree javascript
1 Answers

bst.remove(1) gives the correct output but it doesn't change the tree itself.

That is intended. What you call "the tree itself", is actually the root node. Your code doesn't have a concept of tree in a form of a separate class -- the tree is (only) implied by the root node. As the removal of a node is not a mutation of the removed node, but of other references, and the only reference you have to that root node is the bst variable, you need an assignment to bst. In the extreme case where the last node of a tree is removed, you'll expect bst to become null, so again, an assignment to bst is needed. As this bst variable is not a property of some class instance, you need to manage this assignment "yourself" in the main code.

Here is another way to analyse this situation:

The removeImpl function relies on the caller to attach the returned node at the right place. You can see this happening at every recursive call that is made by removeImpl... for example:

  node.left = this.removeImpl(key, node.left);
  node.right = this.removeImpl(key, node.right);

So we could say that the caller mutates the tree. If removeImpl is itself the caller (of a recursive call), then it performs the mutation itself, but also the initial caller of removeImpl (which is remove) does so:

return this.removeImpl(key, this);

Here we see that the responsibility to do something with the returned node is cascaded to the caller of remove. That caller should apply this principle, and that is were your current code is lacking. We see the call of remove here:

bst.remove(1)

But that call ignores the returned node. That is not how remove is supposed to be called. It should be called like this:

bst = bst.remove(1)

With that change, the code consistently uses the node returned by the remove and removeImpl methods to capture the change.

A two-class system

The above may look too verbose. If you want bst.remove(1) to do the job without any need to assign something to bst, then you should consider a two-class system instead of your current one-class implementation.

You would then rename your current BST class to Node, and create a second class which will be the container class, and can be named BST. When you rename BST to Node, don't forget to use that name also where you create nodes (like in the insert method, new BST should become new Node).

Then add:

class BST {
    constructor() {
        self.root = null; // Now the root is a property, not a global variable
    }
    insert(key) {
        if (self.root == null) self.root = new Node(key);
        else self.root.insert(key);
    }
    remove(key) {
        if (self.root) {
            // Now we mutate the container instance:
            self.root = self.root.remove(key);
        }
    }
}

var bst = new BST();
for (let value of [1, 2, 3, 4]) bst.insert(value);
bst.remove(1);
user_54598390
Related