Recursive Add method for BST using Javascript not working

Question

Below is the implementation of a BST with an insertion function for it. currently, the code wouldn't work; It would just spit out Tree { root: null }

When i tried to debug it, it seems that it successfully adds the new Node to the correct spot, but once it returns from the function, all that data is lost and it ends up not inserting anything.

here is the code:

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

class Tree {
    constructor() {
        this.root = null
    }

    insert(value) {
        const insertHelper = (value, node) => {
            if (node === null) {
                node = new Node(value)
                return null
            } else if (node.value === node.value) {
                console.log("Value exists.")
                return null;
            } else if (node.value < node.value) {
                return this.insertHelper(node, node.right)
            } else {
                return this.insertHelper(node, node.left)
            }
        }

        return insertHelper(value, this.root)
    }

}

var tree = new Tree;
tree.insert(10)
tree.insert(5)

console.log(tree);

trincot · Accepted Answer · 2020-10-16T21:21:15.843

Several issues:

this.root is never modified. Function arguments are passed by value, so if you pass this.root as argument, and the function assigns a new value to the corresponding parameter variable node, this will not affect this.root. The solution is to let the helper function return the new value of the node that is passed as argument, so you can assign it back to the root (or other node).
At several places you compare node.value with node.value. That is a mistake. The comparison should involve value.
The recursive calls pass node as first argument, while the function expects the value as first argument.

Here is the corrected code:

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

class Tree {
    constructor() {
        this.root = null;
    }

    insert(value) {
        const insertHelper = (value, node) => {
            if (node === null) {
                node = new Node(value);
            } else if (node.value === value) {
                console.log("Value exists.");
            } else if (node.value < value) {
                node.right = insertHelper(value, node.right);
            } else {
                node.left = insertHelper(value, node.left);
            }
            return node;
        }
        this.root = insertHelper(value, this.root);
    }
}

var tree = new Tree;
tree.insert(10);
tree.insert(5);
console.log(tree);

NB: use semi-colons explicitly. Relying on the automatic semi-colon insertion is asking for trouble. One day it will hit you.

Recursive Add method for BST using Javascript not working

1 Answers1