Implement a Binary Search Tree in JavaScript

Implement a Binary Search Tree in JavaScript

This is the third of a series of articles on implementing data structures in JavaScript. If you’re new to data structures, be sure to start from the beginning with Stacks .

Analysis

A binary search tree (BST) is a node-based tree data structure in which each node can have at most two children. A BST supports several methods common to any search tree such as contains, insert and depthFirstLog, and delete. We’ll get more into those later on! There are two main ways of representing a BST. I’m going to focus on the method using node objects that have references to their children.

As the name suggests, a BST is just a binary tree, only with the following restrictions placed on where nodes can go.

  • For each node (node1), every value found in the left sub-tree of node1 is less than or equal to the value found in node1.
  • For each node (node1), every value found in the right sub-tree of node1 is greater than or equal to the value found in node1.

That’s not so hard to visualize, but let me reiterate. A BST is just a tree where each left child has a value that’s less than the the parent’s value, and a right child that has a value that’s greater than or equal to the parent’s value.

Methods

BSTs have four main methods:

  1. insert(value): Accepts a value and places in the tree in the correct position.
  2. contains(value): Accepts a value and returns a boolean reflecting whether or not the value is contained in the tree.
  3. depthFirstLog(callback): Accepts a callback and executes it on every value contained in the tree.

and sometimes contains:

  1. delete(value): Accepts a value and deletes that specific value within the BST.

Let’s dive deeper into the BST methods

Insert The insert method performs binary search on the root node, moving to the left child if n is less than the current node or right if n is greater than the current node. This continues until the left or right child does not exist, which is where the new node will then be inserted.

Contains The search operation performs binary search much like the insert operation to determine whether n exists.

Depth First Log The depthFirstLog method accepts a callback and applies the callback to each value in the BST. This means we need (should) recursion to traverse down each BST to apply the callback function to each node.

If you don’t feel comfortable with recursion, I highly suggest you read a beginner article on recursion and take some time to practice every day. You’ll be using recursion to solve complex problems a lot more than you might think!

Pseudocode

The pseudocode for this is very complex and in detail as I didn’t want to skimp on each line, so take the time to slowly go through each and understand what’s going on.

Create BST constructor
  define value, right child and left child

Define insert method on prototype (value)
  Create new node with passed in value
  Create recursive function
    If current node value > value && left child is undefined
      Insert node as left child
    If current node value > value
      Recurse current node left child
    If current node value <value && right child is undefined
      Insert node as right child
    If current node value <value
      Recurse current node right child
  Call recursive function on root node

Define contains method on prototype (value)
  Create variable to hold found node
  Create recursive function
    If current node value is equal to value
      Set variable equal to true
    else if BST left child is !undefined && value < BST value 
      recurse with current node's left child
    else if BST right child is !undefined && value > BST value
      recurse with current node's right child
  Call recursive function on root node
  Return variable of found node

Define depthFirstLog method on prototype (callback)
  Create recursive function
    Use call with callback on BST and BST value
    If left child is not undefined 
      Recurse through left child
    If right child is not undefined
      Recurse through right child
  Call recursive function on root node

Time complexity

If you don’t know much about time complexity, take some time and go learn the basics before you move forward.

Methods on a BST always start at the root node and work their way down, due to this, the maximum time each operation takes is based on how high the tree is. For example a tree with n nodes where there are no right children will take O(n) time, a complete BST however (every level except the last is completely filled, with nodes on the last as left as possible) has the worst case time of O(logn).

  • delete: Linear — O(n), or O(log n) in average case
  • insert: Linear — O(n), or O(log n) in average case
  • contains: Linear — O(n), or O(log n) in average case
  • depthFirstLog: Linear — O(n), or O(log n) in average case

Code

// This Binary Search Tree is implemented using the prototypal pattern

var BinarySearchTree = function(value) {
  var instance = Object.create(BinarySearchTree.prototype);

    instance.value = value;
    // a BST where all values are higher than than the current value.
    instance.right = undefined;
    // a binary search tree (BST) where all values are lower than than the current value.
    instance.left = undefined;

  return instance
};

BinarySearchTree.prototype.insert = function (value) {
  // accepts a value and places in the tree in the correct position.
  var node = BinarySearchTree(value);

  function recurse(bst) {
    if (bst.value > value && bst.left === undefined) {
      bst.left = node;
    } else if (bst.value > value) {
      recurse(bst.left);
    } else if (bst.value < value && bst.right === undefined) {
      bst.right = node;
    } else if (bst.value < value) {
      recurse(bst.right);
    }
  }

  recurse(this);
}

BinarySearchTree.prototype.contains = function (value) {
  var doesContain = false;
  //accepts a value and returns a boolean reflecting whether or not the value is contained in the tree.
  function recurse(bst) {
    if (bst.value === value) {
      doesContain = true;;
    } else if (bst.left !== undefined && value < bst.value) {
      recurse(bst.left);
    } else if (bst.right !== undefined && value > bst.value) {
      recurse(bst.right)
    }
  }

  recurse(this);
  return doesContain;
}

BinarySearchTree.prototype.depthFirstLog = function (callback) {
  //accepts a callback and executes it on every value contained in the tree.
  function recurse(bst) {
    callback.call(bst, bst.value)

    if (bst.left !== undefined) {
      recurse(bst.left)
    }

    if (bst.right !== undefined) {
      recurse(bst.right);
    }
  }

  recurse(this);
}

This post was written by one of the instructors at Banyan Codecamp, a new coding bootcamp designed with a singular goal in mind: turn novice programmers into capable engineers under the leadership of senior engineers. Graduate, make six figures, and study on the beautiful island of Bali. To learn more, visit codeinbali.com.