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