Data Structures in JavaScript: Binary Search Trees

Posted by aut0maat10 on June 13, 2018

This week, I’m going to do a quick implementation of a binary search tree in JavaScript. This first version features a simple add method in order to insert items into the data structure. I will look into other methods (search, delete…) some other time.

Data Structures: Trees

A tree is a data structure with a root node. Each node has child nodes. In a binary tree, each node has at most two children. These children are referred to as left child and right child. This means that smaller values go to the left, and larger values go to the right (of the parent node).

A binary search tree (BST) allows for fast lookup, addition, and removal of items. Binary search trees keep their keys in sorted order, so that lookup can use the principle of binary search.

Implementation

Using JS classes to construct a Node and a Tree, a basic implementation with an add method would look like this:

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

  add(value) {
    // check if there is a root. if not, add new value as root.
    if (this.root === null) {
      this.root = new Node(value);
      break;
    }
    
    let current = this.root;
    
    while(true) {
      if (current.value > value) {
        // go left

        // if there is a left child, run loop again.
        if (current.left) {
          current = current.left;
        }
        // else, place the new node here (to the left of current node).
        else {
          current.left = new Node(value);
          break;
        }
      }
      else {
        // go right

        // if there is a right child, start again
        if (current.right) {
          current = current.right;
        }
        // else, place new node here.
        else {
          current.right = new Node(value);
          break; 
        }
      }
    }
  }
}


// Node class with default (null) values for left and right
class Node {
  constructor( value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

Links:

Data Structures: Trees (HackerRank)

Algorithms (4th Edition): Binary Search Trees

Wikipedia