Functional mixin to add AVL behaviour to a BST node object

avl.mjs

var getBstNode = (value) => ({
  value,
  left: null,
  right: null,
  height: 0,
});

var withAvl = (node, compare) => ({
  ...node,

  insert(value, currentNode) {
    if (currentNode === undefined) {
      currentNode = this;
    }

    if (!currentNode) {
      return withAvl(getBstNode(value), compare);
    }

    var comparisonResult = compare(value, currentNode.value);

    if (comparisonResult < 0) {
      currentNode.left = currentNode.left
        ? currentNode.left.insert(value)
        : withAvl(getBstNode(value), compare);
    } else if (comparisonResult > 0) {
      currentNode.right = currentNode.right
        ? currentNode.right.insert(value)
        : withAvl(getBstNode(value), compare);
    } else {
      return currentNode;
    }

    currentNode = setNodeHeight(currentNode);

    return rebalanceNode(currentNode);
  },

  remove(value, currentNode) {
    if (currentNode === undefined) {
      currentNode = this;
    }

    if (!currentNode) {
      return null;
    }

    var comparisonResult = compare(value, currentNode.value);

    if (comparisonResult < 0) {
      currentNode.left = currentNode.left
        ? currentNode.left.remove(value)
        : null;
    } else if (comparisonResult > 0) {
      currentNode.right = currentNode.right
        ? currentNode.right.remove(value)
        : null;
    } else {
      if (!currentNode.left && !currentNode.right) {
        currentNode.left = null;
        currentNode.right = null;
        return null;
      }

      if (!currentNode.left || !currentNode.right) {
        return currentNode.left || currentNode.right;
      }

      var inOrderSuccessor = currentNode.right;

      while (inOrderSuccessor.left) {
        inOrderSuccessor = inOrderSuccessor.left;
      }

      currentNode.value = inOrderSuccessor.value;
      currentNode.right = currentNode.right.remove(inOrderSuccessor.value);
    }

    currentNode = setNodeHeight(currentNode);

    return rebalanceNode(currentNode);
  },

  print(currentNode, prefix = "", isLeft = true) {
    if (currentNode === undefined) {
      currentNode = this;
    }

    if (!currentNode) {
      return;
    }

    if (currentNode.right) {
      currentNode.right.print(
        currentNode.right,
        `${prefix}${isLeft ? "│   " : "    "}`,
        false
      );
    }

    console.log(`${prefix}${isLeft ? "└── " : "┌── "}${currentNode.value}`);

    if (currentNode.left) {
      currentNode.left.print(
        currentNode.left,
        `${prefix}${isLeft ? "    " : "│   "}`,
        true
      );
    }
  },
});

var getNodeHeight = (node) => (node ? node.height : -1);

var setNodeHeight = (node) => {
  node.height =
    1 + Math.max(getNodeHeight(node.left), getNodeHeight(node.right));
  return node;
};

var getBalanceFactor = (node) =>
  getNodeHeight(node.right) - getNodeHeight(node.left);

var rebalanceNode = (node) => {
  var balanceFactor = getBalanceFactor(node);

  if (balanceFactor < -1) {
    if (getBalanceFactor(node.left) > 0) {
      node.left = rrRotateNode(node.left);
    }

    return llRotateNode(node);
  }

  if (balanceFactor > 1) {
    if (getBalanceFactor(node.right) < 0) {
      node.right = llRotateNode(node.right);
    }

    return rrRotateNode(node);
  }

  return node; // Tree is balanced
};

var llRotateNode = (node) => {
  var newParent = node.left;

  node.left = newParent.right;
  newParent.right = node;

  setNodeHeight(node);
  setNodeHeight(newParent);

  return newParent;
};

var rrRotateNode = (node) => {
  var newParent = node.right;

  node.right = newParent.left;
  newParent.left = node;

  setNodeHeight(node);
  setNodeHeight(newParent);

  return newParent;
};

var numericCompare = (a, b) => a - b;
var avl = withAvl(getBstNode(5), numericCompare);

avl = avl.insert(6);
avl = avl.insert(22);
avl = avl.insert(57);
avl = avl.insert(157);
avl = avl.insert(52);
avl = avl.insert(251);
avl = avl.insert(7);
avl = avl.insert(33);
avl = avl.insert(4);
avl = avl.insert(8);

console.log(avl);

console.log(avl.print());

avl = avl.remove(22);

console.log(avl.print());

avl = avl.remove(33);

console.log(avl.print());