Writing a recursive add method for a Javascript Binary Search Tree

Question

I'm trying to write an add/insert method for a BST in JS, but can't seem to get it working for some reason. My code is here:

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


function BinarySearchTree() {
    this.root = null;

    this.add = function(insertElem){
        let currNode = this.root;

        var recurInsert = function(elem, node){
            if(node == null){
                let newNode = new Node(elem);
                node = newNode;
                console.log("firstNode");
                return undefined;
            }
            else if(elem == node.value){
                console.log("equal val");
                return null
            }
            else if(elem > node.value){
                console.log("go right");
                recurInsert(elem, node.right);
            }
            else{
                console.log("go left");
                recurInsert(elem, node.left);
            }
        }

        recurInsert(insertElem, currNode);
    }
}

Specifically, the line node = newNode doesn't actually set node to newNode. I suspect that this could have something to do with pass-by-value nature of JavaScript, but I'm not completely sure.

Where did I go wrong?

Also, I'm hoping to keep this recursive form for now if possible.

I haven't finished looking it over, but if possible I'd advocate changing the name of the function. Node is a bad name to use considering the Browser already contains a Node prototype object. — zfrisch
– zfrisch, Commented Jun 19, 2018 at 20:01
The add function is supposed to work following the rules of a typical BST, with smaller values on the left, and larger values to the right. If the value already exists in the tree, then it shouldn't be added. — albert
– albert, Commented Jun 19, 2018 at 20:04
I'll try changing the name, I didn't even think of that. Thanks. — albert
– albert, Commented Jun 19, 2018 at 20:04
Hey there, I tried changing all instances of Node to something else, but it still isn't working properly — albert
– albert, Commented Jun 19, 2018 at 20:09

Nina Scholz · Accepted Answer · 2018-06-20 06:35:16Z

2

Basically you need to hand over the object reference to the recursive function, because if not, you create new nodes without linking to the root node.

This code takes an object and the direction as key and checkes the four different dicision to make. If a new node has to be assigned, the object and the key is used.

If a value is smaller or greater than the node's value, the node is used along with the new direction for checking.

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

function BinarySearchTree() {
    this.root = null;
    this.add = function (value) {

        function check(node, direction) {
            if (node[direction] === null) {
                node[direction] = new Node(value);
                console.log('new node', value);
                return;
            }
            if (node[direction].value === value) {
                console.log('equal value', value);
                return;
            }
            if (node[direction].value > value) {
                console.log('go left', node[direction].value);
                check(node[direction], 'left');
                return;
            }
            if (node[direction].value < value) {
                console.log('go right', node[direction].value);
                check(node[direction], 'right');
            }
        }

        check(this, 'root');
    };
}

var tree = new BinarySearchTree;

tree.add(10);
tree.add(5);
tree.add(15);
tree.add(2);
tree.add(4);
tree.add(11);

console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }

An even shorter approach by using a default node.

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

function BinarySearchTree() {
    this.root = null;
    this.add = function (value) {

        function check(node) {
            if (node.value === value) {
                return;
            }
            if (node.value > value) {
                check(node.left = node.left || new Node(value));
                return;
            }
            if (node.value < value) {
                check(node.right = node.right || new Node(value));
            }
        }

        check(this.root = this.root || new Node(value));
    };
}

var tree = new BinarySearchTree;

tree.add(10);
tree.add(5);
tree.add(15);
tree.add(2);
tree.add(4);
tree.add(11);

console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Small example of changing objects vs properties

function assign(o) {      // take object reference as value of o
    o = { bar: 43 };      // assign a new value to o, object keeps it value
    console.log('o', o);  // the reference to object is replaced by an own object
}

function change(o) {      // take object reference as value of o
    o.bar = 41;           // take object reference and assign a new property
    console.log('o', o);  // because of the object reference, o and object has changed
}

var object = { foo: 42 };
console.log('object', object);

assign(object);
console.log('object', object);

change(object);
console.log('object', object);

.as-console-wrapper { max-height: 100% !important; top: 0; }

edited Jun 20, 2018 at 6:35

answered Jun 19, 2018 at 20:53

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

albert Over a year ago

Hey there, so I tried this and it worked. I have a vague understanding of why your answer worked and mine didn't, but could you explain more of what you meant with "hand over the object reference to the recursive function"? I thought that Javascript was pass-by-reference for objects? Why is it that when I passed in this.root could it not assign this.root.right = value?

Nina Scholz Over a year ago

@albert, javascript passes objects by reference, but if you just assign a value to the local variable, the local variable gets a new value, but the object reference is lost. if you use a property, the object reference stays but the change of a property affect both (which id because of the object reference only one object).

albert Over a year ago

Oh I see. So if you change a property of an object the variable loses reference to that object because it's technically now a different object?

Nina Scholz Over a year ago

no, if you change the property of an object, it keeps the reference. otherwise x.y = 42 would not work.

albert Over a year ago

Oh ok, I went back and thought about it some more and finally understand. Basically, I can't write "node = newNode", because I'd be changing what the 'node' variable refers to (a different object now). But if it wrote "node.direction = newNode", I'm not changing what the variable 'node' refers to, I'm just adding the object that it's already pointed to. Is that pretty accurate?

|

Tiago Redaelli · Accepted Answer · 2018-06-19 21:35:08Z

2

The problem is that you need to set the node.right or node.left to the newNode and not node = newNode. Otherwise there is no linking of references and your root will never have any children.

So your insertions should actually be done here, if right.next or left.next is null, rather than on the next recursion.

      else if(elem > node.value){
            console.log("go right");
            if (node.right == null) 
                 node.right = new Node(elem);
            else 
                recurInsert(elem, node.right);
        }
        else{
            console.log("go left");
            if (node.left == null)
                node.left = new Node(elem);
            else 
                recurInsert(elem, node.left);
        }

You can also remove the whole if (node == null) { ... } section, and simply check if the root is null once before starting

if (root == null) {
   root = new Node(insertElem);
   return null;
}

Here is the full code:

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

function BinarySearchTree() {
    this.root = null;

    this.add = function(value) {
        if (this.root == null) {
            this.root = new Node(value);
            return;
        } 
        var recInsert = function(value, node) {
            if (value == node.value) {
                print("equal");
                return;
            }
            if (value < node.value) {
                if (node.left == null) 
                    node.left = new Node(value);   
                else 
                    recInsert(value, node.left);
            }
            else {
                if (node.right == null) 
                    node.right = new Node(value);   
                else 
                    recInsert(value, node.right);
            }
        }
        recInsert(value, this.root);
    } 

    this.print = function() {
        if (this.root != null) {
           var rec = function(node) {
               if (node == null) 
                   return;
               rec(node.left);
               print(node.value);
               rec(node.right);
           }
           rec(this.root);
        }   
    }
}

edited Jun 19, 2018 at 21:35

answered Jun 19, 2018 at 20:13

Tiago Redaelli

6306 silver badges17 bronze badges

4 Comments

albert Over a year ago

Hey there, just finished trying this and it didn't seem to work still

Tiago Redaelli Over a year ago

did you set the root on first also?

albert Over a year ago

I did an if(currNode == null){...} outside of my recursive function, then an else{resurInsert(insertElem, currNode)}, where currNode = this.root

Tiago Redaelli Over a year ago

Okay, I think you must be doing something wrong, included full code.

Collectives™ on Stack Overflow

Writing a recursive add method for a Javascript Binary Search Tree

2 Answers 2

6 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related