Creating an iterative function to add nodes to a Binary Search Tree in JavaScript

Question

Creating an iterative function to add nodes to a Binary Search Tree in JavaScript

Having trouble getting my add/insert method for a BST in JS to work properly. Check out my code below:

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);
    }
}

Having an issue with node = newNode not setting node correctly to newNode. Possible pass-by-value problem in JavaScript?

Can someone help me find the mistake?

Prefer to keep it recursive for now.

javascript data-structures

Answer 1

Answer №1

Essentially, in order to avoid creating new nodes without linking them to the root node, you must pass the object reference to the recursive function.

This particular code handles an object with a key representing direction and checks the four different decisions that need to be made. If a new node needs to be assigned, both the object and the key are utilized.

If the value is less than or greater than the current node's value, the node along with the new direction is used for further evaluation.

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 alternative, more concise approach involves utilizing 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; }

A brief example illustrating the difference between 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; }

Answer 2

Essentially, in order to avoid creating new nodes without linking them to the root node, you must pass the object reference to the recursive function.

This particular code handles an object with a key representing direction and checks the four different decisions that need to be made. If a new node needs to be assigned, both the object and the key are utilized.

If the value is less than or greater than the current node's value, the node along with the new direction is used for further evaluation.

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 alternative, more concise approach involves utilizing 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; }

A brief example illustrating the difference between 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; }

Answer 3

Answer №2

The issue lies in the necessity to assign the newNode to node.right or node.left, rather than simply setting node = newNode. This results in a failure to establish references and ultimately leads to the root node lacking any children.

Therefore, it is crucial that insertions are made at the point where right.next or left.next is null, rather than waiting for 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);
        }

In addition, the entire if (node == null) { ... } section can be eliminated by checking if the root is null just once before commencing.

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

Below is the complete code snippet:

    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);
        }   
    }
}

Answer 4

The issue lies in the necessity to assign the newNode to node.right or node.left, rather than simply setting node = newNode. This results in a failure to establish references and ultimately leads to the root node lacking any children.

Therefore, it is crucial that insertions are made at the point where right.next or left.next is null, rather than waiting for 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);
        }

In addition, the entire if (node == null) { ... } section can be eliminated by checking if the root is null just once before commencing.

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

Below is the complete code snippet:

    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);
        }   
    }
}

Creating an iterative function to add nodes to a Binary Search Tree in JavaScript

Answer №1

Answer №2

Similar questions

Retrieving a designated set of attributes for elements chosen using an element selector

The word-break CSS property is ineffective in this situation

Sharing variables between different routes in ExpressJS

The function is not able to fetch the value from the Amazon S3 file, however, it is printed

Tips on utilizing AngularJS $http for transferring multipart/form-data

Transform ajax functionality into jquery

Retrieving the positions of a mesh as it looks towards an object in three.js

Comparison Between Angular 4 `ng serve --prod` and `ng serve` Commands

Can a string starting with certain values be omitted?

Utilizing React hook form to submit arrays with the help of React server actions

Receiving blank response from jQuery POST request

What causes my Excel file to become corrupted when inputting new data?

JavaScript is incorrectly showing the array as empty despite containing strings

Is there a way to sequentially execute requests in a loop?

Resolving the issue of nested modals within Bootstrap

In Snowflake, SQL error handling block fails to execute

Why do I need to double-click? (JavaScript onclick event handler)

jQuery - selecting child elements with a strict hierachy restrictions

Combining arrays within an array using the concat method in JavaScript instead of the push method

Perform an operation in JQuery after a different operation has been completed