Javascript Binary Search Tree methods not working

Question

I am trying to build this simple Javascript Binary search tree. I have simply created the addItem method for the tree, but no item seems to get added to the tree. I have divided the addItem method into several other methods to ensure that the tree reference is passed properly without any errors. I think the problem is occurring in the addNode recursive calls.

Below the is the given code:

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


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

    addNode(node, item){
        if(node==null){
            node=new Node(item);
        }
        else if(item<=node.value){
            this.addNode(node.left, item);

        }
        else {
            this.addNode(node.right, item);
        }
    }

    addFunc(tree, item){

        this.addNode(tree.root, item);
    }

    addItem(item){
        this.addFunc(this, item);
     }


}


let bst = new BST();
bst.addItem(5);
bst.addItem(43);
bst.addNode(12);

console.log(bst); // shows BST{root:null}

I can see why this doesn't do anything but I'm utterly bewildered at what you're trying to accomplish. It looks like maybe you don't realize that you have to set instance variables using `this` in JavaScript as opposed to a language like Java. But who knows.... your code just doesn't make any sense whatsoever. — john_omalley, Apr 22 '18 at 15:33
@RandyCasburn the 'addFunc' has been called inside the addItem method, the idea is to just call bst.addItem(item). and inside the addItem method i did called the addFunc method — raiyan106, Apr 22 '18 at 15:34
Yeah, saw it eventually, I think I was just perplexed as John stated. — Randy Casburn, Apr 22 '18 at 15:35
@john_omalley can you rewrite the code keeping the structure that i created? — raiyan106, Apr 22 '18 at 15:36
@raiyan106 - please see my answer. I think you'll understand. — Randy Casburn, Apr 22 '18 at 18:06
@raiyan106 Try this class I have created https://www.npmjs.com/package/@dsinjs/binary-tree it has alot of basic + extra functions — Siddhesh Kulkarni, Nov 29 '20 at 19:27

score 0 · Answer 1 · answered Apr 22 '18 at 15:40

0

One of the problem is in function addNode() at if(node==null){node=new Node(item);}

node is passed as a parameter, which means when this.addNode(tree.root, item); is called

node.a = 5 changes value of tree.root.a to 5
node = 5 just changes the value of this node parameter to 5 but not the actual argument that is tree.root value is not assigned to 5.

More info

answered Apr 22 '18 at 15:40

amitdigga

6,550
4
26
31

I see, then how am i supposed to refer the tree.root variable in this method? – raiyan106 Apr 22 '18 at 15:43
If you want to assign `root` a new reference in another function then you can pass `tree` as a parameter and and check can assign `tree.root = {}` a new value. – amitdigga Apr 22 '18 at 15:46
what if i just assign this.root={} instead of this.root=null while defining the constructor? wont it be the same thing? – raiyan106 Apr 22 '18 at 15:52
I dont know BST, but only javascript. So I pointed out that problem. Depends upon that `root` should be init with `{}` or `null`, but it wont solve problem as pointed in `addNode()`. – amitdigga Apr 22 '18 at 15:56

Randy Casburn · Answer 2 · 2018-04-22T18:12:11.457

First, you've not assigned anything as the root of your tree. Your intent was there with this.root. Next, your logic has you recursing a method rather than recursing your tree.

While you call the addNode() method for each value, you always test the root of your tree for > and < values. So this code will only ever overwrite a single .left or .right value. So recursing your function internally doesn't really do what you expect.

The solution is to recurse the tree looking for the correct slot for the value that is passed into the function.

I've re-written your code a bit and taken some liberties with the API. For instance, creating a new BST will require the starting value to be passed into the constructor (this just helps simplify the code a bit). Next, you'll notice no more recursive functions. The recursive calls are replaced with a while loop that finds the appropriate node to add the new node.

This code actually builds the tree where as your attempt only builds a single level.

Edit refactored into search function

class Node {
  constructor(value) {
    this.value = value;
    this.left = {};
    this.right = {};
  }
  show() {
    console.log(this.value);
  }
}


class BST {
  constructor(value = 0) {
    this.root = new Node(value);
  }

  addNode(item) {
    Object.assign(this.search(item), new Node(item));
  }
  findLeftChild(item) {
    return this.search(item).left.value;
  }

  search(item) {
    let found = false;
    let foundNode = this.root;
    while (!found) {
      if (foundNode.value === item) {
        break;
      } else if (foundNode.value > item) {
        foundNode = foundNode.left;
        found = foundNode.value === undefined;
      } else if (foundNode.value < item) {
        foundNode = foundNode.right;
        found = foundNode.value === undefined;
      }
    }
    return foundNode;
  }

  addItem(item) {
    this.addNode(item);
  }
}


let bst = new BST(5);
bst.addItem(43);
bst.addItem(12);
bst.addItem(6);
bst.addItem(66);
bst.addItem(22);
bst.addItem(4);
bst.addItem(3);
bst.addItem(2);
bst.addItem(1);

console.log("Found: 17 ", bst.search(17).value !== undefined);
console.log("find value less than 12: " + bst.findLeftChild(12));
console.log(JSON.stringify(bst, null, 2)); // shows BST{root:null}

Javascript Binary Search Tree methods not working

2 Answers2