Implement a Binary Search Tree in JavaScript

Data Structures
September 22, 2016

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 this article 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 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); }

Having worked across sites raking in over 50 billion website visits annually, Michael Mitrakos can help your business to crush the web game with an award winning website.

I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!


More Blog Posts