AVL Tree implementation: Insert function – Reference get twisted

I got the bug when adding 13 to the tree, the left and right pointer of node 10 have reference back to the root, and create cycle reference.

I think it’s because I understand Javascript syntax wrong.

code (open the console)

function rotLeft(node) {
  const parentNodeCopy = copyObj(node);
  const parentRightLeftChild =
    node.right.left !== null ? copyObj(node.right.left) : null;
  parentNodeCopy.right = parentRightLeftChild;

  node = node.right;
  node.left = parentNodeCopy;

  return node;
}

function rotRight(node) {
  const parentNodeCopy = copyObj(node);
  const parentLeftRightChild =
    node.left.right !== null ? copyObj(node.left.right) : null;
  parentNodeCopy.left = parentLeftRightChild;
  node = node.left;
  node.right = parentNodeCopy;

  return node;
}

function rebalance(node) {
  const bFact = threshold(node);

  if (bFact > 1) {
    if (threshold(node.left) < 0) node.left = rotLeft(node.left);
    node = rotRight(node);
  } else if (bFact < -1) {
    if (threshold(node.left) > 0) node.right = rotRight(node.right);
    node = rotLeft(node);
  }

  return node;
}

function insert(node, val) {
  if (node === null) return;

  if (val <= node.val) {
    if (node.left !== null) insert(node.left, val);
    else node.left = new TreeNode(val);
  } else {
    if (node.right !== null) insert(node.right, val);
    else node.right = new TreeNode(val);
  }

  return rebalance(node);
}

Any suggestion?

Answer

The problem is that you don’t use the returned node reference from the recursive call of insert. insert may return a different node than the one it got as argument. By not assigning it back to node.left or node.right, the latter will keep a reference to the non-cloned node, giving you an inconsistent tree.

So change this:

if (node.left !== null) insert(node.left, val);

to this:

if (node.left !== null) node.left = insert(node.left, val);

Do the same with the mirrored case.

Other remarks

Unrelated to your question:

1. It should not be necessary to create clones of nodes. Rotations can be implemented by just mutating the existing nodes.

2. Retrieving the height dynamically each time you need it will kill the performance of this implementation. It is better to store the height as a property of a node and keep it updated. The best is to store the balance factor. With some nifty logic you can keep the balance factors up to date without having to query the heights of nodes. It is possible with just knowing the balance factor of the children, and which rotation is being performed.