Object reference get twisted

JavaScript
1

I am implementing AVL Tree by Javascript .

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.

My code here (open the console to see the result)

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);
}
2

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.