0

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)

4
  • 1
    You've failed to declare a number of variables, but also aren't keeping an updated reference of root anywhere so it always just returns immediately on insert. It seems you are attempting to make a Tree class in which case the modern class syntax will be clearer. see: Classes Commented Nov 23, 2022 at 10:45
  • 1
    Added to that if (value < current) doesn't make sense as you actually want to compare to the current node's data property so if (value < current.data) Commented Nov 23, 2022 at 10:55
  • 1
    Here is a rough refactoring of your existing code into a Class jsfiddle. It's not an answer as I don't have time and doesn't address many of the issues in your code, but it may point you in the right direction. You will want to refactor Node to be a class as well, and will need to deal with balancing the tree. Commented Nov 23, 2022 at 11:02
  • @trincot I do give feedback, but I didn't know I was supposed to mark an answer as accepted. will do from now on. Thanks for the heads up. Commented Nov 23, 2022 at 15:07

1 Answer 1

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
            }
        }
    };
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.