DSA Binary Search Tree - Insert function not working fully

27 Views Asked by At

I'm working through binary search trees in The Odin Project (TOP)(https://www.theodinproject.com/lessons/javascript-binary-search-trees) and I'm having trouble with the insert function.

I believe the function inserts the node in the correct place in the BST but it does so even before I even call the insert function. The prettyPrint() function, which is given by (TOP) returns an error Cannot read properties of undefined. If I remove the insert function, everything works fine. Am I traversing the tree incorrectly?

const createNode = (data, left = null, right = null) => {
  return {
    data: data,
    left: left,
    right: right,
  };
};

const tree = (arr) => {
  const sortedArr = mergeSort(removeDuplicates(arr));
  root = buildTree(sortedArr);
  
  // Problem starts here
  const insert = (val, root = this.root) => {
    // base case: if null leaf is reached, insert new node with val.
    if (root === null) {
      const newNode = createNode(val);
      return newNode;
    }

    // traverses down the tree branch until it reaches a null leaf.
    if (val < root.data) {
      root.left = insert(val, root.left);
    } else {
      root.right = insert(val, root.right);
    }
    return root;
    // End of problem
  };
  return { root, insert };
};


const buildTree = (sortedArr, start = 0, end = sortedArr.length - 1) => {
  if (start > end) return null;

  let mid = Math.floor((start + end) / 2);

  let root = sortedArr[mid];
  let node = createNode(root);

  node.left = buildTree(sortedArr, start, mid - 1);
  node.right = buildTree(sortedArr, mid + 1, end);
  return node;
};

const removeDuplicates = (arr) => {
  const arrNoDups = [];
  Array.from(arr).forEach((i) => {
    if (!arrNoDups.includes(i)) {
      arrNoDups.push(i);
    }
  });
  return arrNoDups;
};

// merge sort function
const mergeSort = (arr) => {
  if (arr.length < 2) return arr;

  const mid = Math.floor(arr.length / 2);
  const leftArr = arr.slice(0, mid);
  const rightArr = arr.slice(mid);
  return merge(mergeSort(leftArr), mergeSort(rightArr));
};

const merge = (leftArr, rightArr) => {
  const sortedArr = [];
  let countL = 0;
  let countR = 0;
  while (countL < leftArr.length && countR < rightArr.length) {
    if (leftArr[countL] < rightArr[countR]) {
      sortedArr.push(leftArr[countL]);
      countL++;
    } else {
      sortedArr.push(rightArr[countR]);
      countR++;
    }
  }

  while (countL < leftArr.length) {
    sortedArr.push(leftArr[countL]);
    countL++;
  }

  while (countR < rightArr.length) {
    sortedArr.push(rightArr[countR]);
    countR++;
  }
  return sortedArr;
};

// Console log tree visual
const prettyPrint = (node, prefix = '', isLeft = true) => {
  if (node === null) {
    return;
  }
  if (node.right !== null) {
    prettyPrint(node.right, `${prefix}${isLeft ? '│   ' : '    '}`, false);
  }
  console.log(`${prefix}${isLeft ? '└── ' : '┌── '}${node.data}`);
  if (node.left !== null) {
    prettyPrint(node.left, `${prefix}${isLeft ? '    ' : '│   '}`, true);
  }
};

const newTree = tree([1, 2]);
console.log(newTree); // console logs 1 => 2 (right) => 0 (left) even before the newTree.insert(0) line below.
console.log(newTree.insert(0));
console.log(newTree);
// prettyPrint(newTree);
0

There are 0 best solutions below