Binary search tree - iterative insert method leaves tree empty

Question

I tried to create the insert method for a binary search tree, but 'this.root' remains null.

My logic is:

As long as current (which at the beginning is this.root) is not null, continue to update the current variable, by comparing it with the value we want to insert (if it's greater or less). When current is null, we assign it the new Node:

class Node {
    constructor(value){
        this.value = value
        this.left = null
        this.right = null
    }
}

class BST {
    constructor(){
        this.root = null
        this.count = 0
    }

    insert(value){
        this.count++
        let current = this.root;
        while(current){
            if(value<current){
                current=current.left
            }
            if(value>current){
                current=current.right
            }
        }
        current = new Node(value);
    }    
}

let Binst = new BST(10);
Binst.insert(22)
Binst.insert(12)
Binst.insert(4)
console.log(Binst)

score 1 · Accepted Answer · answered Aug 05 '22 at 12:18

There are these issues:

Comparing value with current is not right: that is comparing a number with an object. You need to compare with current.value
In the main program you call the BST constructor with an argument, but the constructor does not expect an argument. Although you could adapt the constructor to take that argument, it is better to not pass an argument to the constructor and have an extra call of insert in your main program.
current = new Node(value) will not change the tree. It only assigns a new node to a local variable. In order to extend the tree, you need to assign the new node to a left or right property of an existing node (or to the root property of the BST instance). Assigning to a variable never mutates your object structure.
this.root is never assigned anything else after its initialisation with null. Again, assigning to current, is never going to change this.root.
Because of the previous points, you need to stop your loop one iteration earlier -- when current points to the node that is about to get a new child. And you also need to deal separately with the case where the new node must become the root of the tree.

The following are just suggestions, not problems:

It is better practice to separate your statements with semicolons. There is the automatic semicolon insertion algorithm, but you wouldn't be the first to fall in one if its traps. Better take control over it yourself.
It is common practice to name variables with an initial capital when they are classes (constructors), but for instances a lower case initial letter is commonly used. So binst or bIntst instead of Binst. I would even suggest a more readable name, like tree.

Here is the corrected code:

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BST {
    constructor() {
        this.root = null;
        this.count = 0;
    }

    insert(value) {
        this.count++;
        let current = this.root;
        if (!current) {
            this.root = new Node(value);
            return;
        }
        while (true) {
            if (value < current.value){
                if (current.left) {
                    current = current.left;
                } else {
                    current.left = new Node(value);
                    return;
                }
            }
            if (value > current.value) {
                if (current.right) {
                    current = current.right;
                } else {
                    current.right = new Node(value);
                    return;
                }
            }
        }
    }
}

let tree = new BST();
tree.insert(10);
tree.insert(22);
tree.insert(12);
tree.insert(4);
console.log(tree);

Binary search tree - iterative insert method leaves tree empty

1 Answers1