Implementing a binary search tree in JavaScript

Tree data structure

A tree is a collection of nodes connected by some edges. By convention, each node of the tree Save some data and references to its child nodes.

Binary Search Tree

A binary search tree is a binary tree in which nodes with smaller values ​​are stored on the left and nodes with smaller values ​​are stored on the left. Higher values ​​are stored on the right.

For example, the visual representation of a valid BST is -

     25
   /   \
  20   36
 / \   / \
10 22 30 40

Now let us implement our own binary search tree in JavaScript language.

Step 1: Node Class

This class will represent a single node that exists at each point in the BST. BST Nothing Rather, it is a collection of nodes that store data and subreferences placed according to rules. As mentioned above.

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};

To create a new Node instance we can call this class with some data -

const newNode = new Node(23);

This will create a new Node instance with its data set to 23 and both left and right references is null.

Step 2: Binary Search Tree Class:

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

This will create the Binary Search Tree class, which we can call using the new keyword to create a tree instance.

Now that we have done the basics, let's go ahead and insert a new node at the correct location (according to the BST rules described in the definition).

Step 3: Insert nodes in BST

class BinarySearchTree{
   constructor(){
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};

Example

Full binary search tree code:

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};
class BinarySearchTree{
   constructor(){
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};
const BST = new BinarySearchTree();
BST.insert(1);
BST.insert(3);
BST.insert(2);

The above is the detailed content of Implementing a binary search tree in JavaScript. For more information, please follow other related articles on the PHP Chinese website!