JavaScript: How to implement Binary Search Tree

Question

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.

Hello and welcome to StackOverflow, It says that myRoot is not defined yet! are you sure that myRoot is defined correctly? — Ali Kianoor
– Ali Kianoor, Commented Jun 14, 2020 at 18:12

Ehsan Nazeri · Accepted Answer · 2020-06-14 16:46:43Z

1

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']
    }
  }

answered Jun 14, 2020 at 16:46

Ehsan Nazeri

8111 gold badge7 silver badges10 bronze badges

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

Comments

Bagel03 · Accepted Answer · 2020-06-14 16:55:40Z

0

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

answered Jun 14, 2020 at 16:55

Bagel03

7258 silver badges28 bronze badges

Collectives™ on Stack Overflow

JavaScript: How to implement Binary Search Tree

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related