0

Started writing the removal function for an unbalanced BST structure. Manually running some tests for the first case (node has no children). Decided to run it on a tree of size 1 (just the root), and for some reason it does not seem to be reassigning the root to null the way I'm expecting it to on line 3 of this statement:

return direction ?
  parent[direction] :
  node = null;

Then when I run inOrderTraversal on the single node tree, which should just console.log each node, and return undefined for a null tree (what I'm expecting) it simply prints the 55 as it does before the removal.

It seems to be working for all other cases where the node to remove has no children.

Here's the fiddle: https://jsfiddle.net/uvdrmwh0/6/

And the code:

"use strict";

function Node(value, left = null, right = null) {
  return {
    value,
    left,
    right
  };
}

function insert(x, root) {
  let currNode = root;
  while (currNode) {
    if (x < currNode.value) {
      if (currNode.left) {
        currNode = currNode.left;
      } else {
        currNode.left = Node(x);
        return;
      }
    } else if (x > currNode.value) {
      if (currNode.right) {
        currNode = currNode.right;
      } else {
        currNode.right = Node(x);
        return;
      }
    } else if (x === currNode.value) {
      throw new Error("cannot insert node with the same value as an existing node");
    } else {
      throw new Error("undefined behavior in insert");
    }
  }
  throw new Error("failed to insert");
}

function remove(x, node, parent = null, direction = null) {
  if (node === null) return;
  if (node.value === x) {
    if (!node.left && !node.right) {
      return direction ?
        parent[direction] = null :
        node = null;
    } else if (node.left && !node.right) {
        //TODO
    }
    //TODO
  }
  direction = x < node.value ? "left" : "right";
  remove(x, node[direction], node, direction);
}

function inOrderTraversal(node) {
  if (node === null) return;
  inOrderTraversal(node.left);
  console.log(node.value);
  inOrderTraversal(node.right);
}

function BinarySearchTree(seed) {
  if (!Array.isArray(seed)) {
    throw new Error("BinarySearchTree must be seeded with an array");
  }
  let root = Node(seed[0]);
  seed.slice(1).forEach(x => {
    insert(x, root);
  });
  return root;
}

let bst = BinarySearchTree([55]);
inOrderTraversal(bst);
console.log("---------after removal---------");
remove(55, bst);
inOrderTraversal(bst);

Update:

I've noticed things like this work:

let x = { a: 1 };
function changeProperty(obj, key, newValue) {
  obj[key] = newValue;
}
changeProperty(x, "a", "hello");
console.log(x.a); //prints hello

But this doesn't:

function reassignObject(obj) {
    obj = { a: "some new value" };
}
reassignObject(x);
console.log(x.a); //still prints hello

It seems you can reassign properties of an object (pointers within an object) and it will change the outside reference, but reassigning the reference to the object itself doesn't?

Jackson Lenhart
  • 630
  • 3
  • 7
  • 19

1 Answers1

2

The following change should make it work:

console.log("---------after removal---------");
bst = remove(55, bst); //change here

The changes to node happen locally in remove function. So you should set the bst to whatever is received back from remove function.

The important thing to understand here is how does javascript pass the arguments. I hope this helps.

Shridhar R Kulkarni
  • 6,653
  • 3
  • 37
  • 57