Understanding Binary Search Trees with Js

A binary Search Tree is one of the most popular and essential Tree Data structures. It is not only important from an Interview standpoint but their application and performance during insertion, searching, and adding new elements is also very significant.

In this blog, we will be able to understand the Binary search tree, its importance, application, operations, advantages, and time complexity.

What is a Binary Search Tree?

A tree data structure is said to be a Binary tree when its node has only children not more than two and follows specific rules:-

• the left sub-tree has values lower than the parent node.
• the right sub-tree has values greater than the parent node.
• each sub-tree is its own binary search tree.

The image below is the graphical presentation of the binary search tree. If you notice, the tree has a root node with a value of 8 and all the numbers that are less than the root node value are on the left and all the numbers larger are on the right side of the tree.

Also read, Easy Explanation of Linked list Data Structure in JavaScript

Implementation of various BST Operations with JavaScript

Since BST is a type of Binary Tree, the same operations are performed in BST. The operations associated with a BST are searching, inserting, deleting, and traversal.

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

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

let tree = new BinarySearchTree();

Insertion

This method is used to add the elements in the Binary search tree:-

• Create a new node
• Starting at the root
  • Check if there is a root, if not – the root now becomes that new node!
  • If there is a root, check if the value of the new node is greater than or less than the value of the root
  • If it is greater
    • check to see if there is a node to the right
    • If there is, move to that node and repeat these steps
    • If there is not, add that node as the right property
  • If it is less
    • Check to see if there is a node to the left
    • If there is, move that node and repeat these steps
    • If there is not, add that node as the left property

insert(value) {
  let newNode = new Node(value);
  if (this.root == null) {
    this.root = newNode;
    return this;
  } else {
    let curr = this.root;
    while (true) {
      if (value == curr.value) return undefined;
      if (value < curr.value) {
        if (curr.left === null) {
          curr.left = newNode;
          return this;
        } else {
          curr = curr.left;
        }
      } else if (value > curr.value) {
        if (curr.right === null) {
          curr.right = newNode;
          return this;
        } else {
          curr = curr.right;
        }
      }
    }
  }
}

Also read, Where Non-Techies Can Get With the Programming

Searching

This method is used to find the element present in the Binary search tree:-

• Starting at the root
  • Check if there is a root, if not – we’re done searching!
  • If there is a root, check if the value of the new node is the value we are looking for, if found it, we’re done!
  • If not, check to see if the value is greater than or less than the value of the root.
  • If it is greater
    • Check to see if there is a node to the right
    • If there is, move to that node and repeat these steps
    • If there is not, we’re done searching!
  • If it is less
    • Check to see if there is a node to the left
    • If there is, move to that node and repeat these steps
    • If there is not, we’re done searching!

find(value) {
  if (this.root == null) {
    return false;
  }

  let curr = this.root;
  let found = false;
  while (curr && !found) {
    if (value < curr.value) {
      curr = curr.left;
    } else if (value > curr.value) {
      curr = curr.right;
    } else {
      found = true
    }
  }
  return found;
}

Note – Tree Traversal and Deletion operation is itself a big topic and needs a separate blog to explain, so please stay tuned, will soon have a new article on Traversal and Deletion operation using js.

Also read, Simple Explanation of Stack and Queue with JavaScript

Applications of Binary Search Trees

• Binary Search Trees are used for indexing and multi-level indexing of files.
• They are helpful in maintaining a sorted data stream.
• Tree Map and Tree Set data structures are implemented with the help of self-balancing BSTs.

Advantages

• Searching and storing any element in the Binary Search tree is very easy as we always have clue about which subtree has the desired element.
• As compared to Array and Linked List data structures, insertion, searching and deletion operations are faster in the Binary search tree.

The complexity of the Binary Search Tree

Time Complexity

Space Complexity

Also read, Introduction to Tree Data Structure

Final Words

I hope you like the article, please comment and share with your friends and bookmark this website, and also do check our detailed articles on Data structure, Javascript, and programming.