CODEWITHSUNDEEP
javascriptdata-structures
Fun Planet
Fun Planet

Reputation: 73

JavaScript: How to implement Binary Search Tree

I am implementing Binary Search Trees in JavaScript, but while writing the insert function, some error is occuring (most probably in the RECURSION).

Here is my code:

class BinarySearchTree {
  constructor() {
    this.length = 0;
    this.root = null;
  }
  insert(elem) {
    if (!this.root) {
      //If root is null then this is the root.
      this.root = new BSTNode(elem);
    } else {
      let newNode = new BSTNode(elem);
      let myRoot = this.getParent(this.root, elem)
      console.log(myRoot);

      if (myRoot[1] == 'left') myRoot[0].left = newNode;      //Error Line
      else myRoot[0].right = newNode;

      this.nodes.push(newNode);
      this.arr.push(elem);
    }
    this.length++
  }
  getParent(root, elem) { // the argument 'root' is ambiguous, but it is for the user

    if (elem < root.value) {
      if (root.left!==null) this.getParent(root.left, elem); 
      else return [root, 'left'];
    } else {
      if (root.right!==null) this.getParent(root.right, elem);
      else return [root, 'right']
    }
  }
}
class BSTNode {
  constructor(val) {
    this.value = val;
    this.left = null; //Left Node
    this.right = null; //Right Node
  }
}

There are two classes; namely BinarySearchTree and BSTNode.

The Error:
Uncaught TypeError: Cannot read property '1' of undefined

I am unable to find the mistake.

Note that other solutions to do the same thing is also welcome.

Upvotes: 2

Views: 238

Answers (2)

Bagel03
Bagel03

Reputation: 715

It should be:

getParent(root, elem) { // the argument 'root' is ambiguous, but it is for the user

    if (elem < root.value) {
      if (root.left!==null) return this.getParent(root.left, elem); 
      else return [root, 'left'];
    } else {
      if (root.right!==null) return this.getParent(root.right, elem);
      else return [root, 'right']
    }
  }

Without returing those values, it will do the work to find the node, but not return it. Most recurive functions return themselves, like: function foo(){return foo()}

Upvotes: 0

Ehsan Nazeri
Ehsan Nazeri

Reputation: 801

you should return the result of this.getParent(root.left, elem); and this.getParent(root.right, elem); 

getParent(root, elem) { // the argument 'root' is ambiguous, but it is for the user

    if (elem < root.value) {

      if (root.left!==null) return this.getParent(root.left, elem); 
      else return [root, 'left'];
    } else {
      if (root.right!==null) return this.getParent(root.right, elem);
      else return [root, 'right']
    }
  }

Upvotes: 1

Related Questions