I'm trying to make a binary search tree. If I start with an array my function makes a binary search tree out of that array (everything fine here). like for an array like let a = [2,4,5,3,9,7,3,8,5]; the tree looks like the picture. my problem is with the insert() function. If I start with an empty array and add a node to it, it works. However, when I add a second node, that second node won't be added to my tree, and my tree is shown as having only 1 node in it (the root node). Here the snippet:
const Node = (data, left = null, right = null) => {
return {data, left, right};
};
const Tree = array => {
const remDupsAndSort = array => {
const mergeSort = array => {
if(array.length <= 1) return array;
let leftArr = array.slice(0, array.length / 2);
let rightArr = array.slice(array.length / 2);
return merge(mergeSort(rightArr), mergeSort(leftArr))
};
const merge = (leftArr, rightArr) => {
let sorted = [];
while(leftArr.length && rightArr.length){
if(leftArr[0] < rightArr[0]){
sorted.push(leftArr.shift());
}else{
sorted.push(rightArr.shift());
}
};
return [...sorted, ...leftArr, ...rightArr]
};
return mergeSort([... new Set(array)])
};
array = remDupsAndSort(array);
const buildTree = (array, start, end) => {
if(start > end) return null;
let mid = Math.floor((start + end) / 2);
let node = Node(array[mid]);
node.left = buildTree(array, start, mid - 1);
node.right = buildTree(array, mid + 1, end);
return node;
};
const insert = value => {
if(!root) return root = Node(value);
current = root;
while(current){
if(value < current){
current = current.left
}else{
current = current.right
}
}
current = Node(value)
// if(!current){
// current = Node(value)
// // }else{
// if(value < current){
// current.left = insert(value, current.left)
// }else{
// current.right = insert(value, current.right)
// }
// }
return root
};
const prettyPrint = (node = root, prefix = '', isLeft = true) => {
if(node){
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);
}
}else{
console.log(node)
}
}
let root = buildTree(array, 0, array.length - 1);
return {root, prettyPrint, insert}
};
let a = [2,4,5,3,9,7,3,8,5];
let b = [];
let c = [1,2,4,5,6,7]
let f = Tree(a)
let d = Tree(b)
let e = Tree(c)
d.insert(4)
// d.insert(8) ---> doesn't work
// d.prettyPrint()
// f.insert(1) ---> doesn't work
f.prettyPrint()
// e.prettyPrint()
// console.log(d.root)
if I run d.prettyPrint() I'll get └── 4 just as expected. But if I run d.insert(8) after that 8 isn't added to the tree and the code returns └── 4 again. To make matters more confusing if I console.log(d.root) it returns null even though my prettyPrint function returns └── 4 as the root.
Clearly I expect the nodes be added to the tree. On one of my attempts I tried to write the code like this:
const insert = (value, current = root) => {
if(!current){
current = Node(value)
}else{
if(value < current){
current.left = insert(value, current.left)
}else{
current.right = insert(value, current.right)
}
}
return current
};
even though I assigned current = root the code returned null for d.insert(4)
rootanywhere so it always just returns immediately on insert. It seems you are attempting to make aTreeclass in which case the modern class syntax will be clearer. see: Classesif (value < current)doesn't make sense as you actually want to compare to the current node'sdataproperty soif (value < current.data)Nodeto be a class as well, and will need to deal with balancing the tree.