# insert() function doesn't add nodes to the binary search tree

## insert() function doesn't add nodes to the binary search tree

Contents

Problem Description:

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

## Solution – 1

There are these issues in your `insert` function:

• `current` is implicitly defined as a global variable — this wouldn’t parse in strict mode. It should be declared as a local variable, using `let`
• The value is compared with a node object instead of with the data of that node. So `value < current` should be changed to `value < current.data`
• The assignment of the new node object to `current` — after the loop — will not mutate the tree. It merely assigns that object to that variable. Such assignment can never change the tree, just like `current = current.right` does not mutate the tree either. You need instead to assign the new node to either the `left` or `right` property of the parent of `current`. So this assignment should happen one step earlier.

Correction:

``````   const insert = value => {
if(!root) return root = Node(value);
let current = root; // Define with `let`
while(current){
if(value < current.data){ // Compare with the data, not the node
// Mutate the parent node when inserting
if (!current.left) return current.left = Node(value);
current = current.left
}else{
if (!current.right) return current.right = Node(value);
current = current.right
}
}
};
``````
Rate this post
We use cookies in order to give you the best possible experience on our website. By continuing to use this site, you agree to our use of cookies.