Binary Search Trees in JavaScript

Gianfranco Nuschese
4 min readFeb 20, 2020

--

An ancient tome of advertisements.

Before the advent of cellphones and the internet, we used these things called phone books. Most of you probably know what a phone book is, but just in case: a phone book is a directory where businesses pay to list their phone numbers, usually arranged by type of business, and then alphabetically within each section.

Let’s say you hear from a friend that they used a service called “Roach-B-Gone”, but they forgot the number. Since it’s 1991, we have to look in the phone book. We open it up to around the halfway point and see an listing for “Larry the Locksmith”. We’re in the “Locksmith” section, and we need to get to the “Pest Control” section. We know we need search toward the right half of the book, so we effectively eliminate the entire left half of the book.

If we flip to the halfway point of the right half of the book, we end up at the “Towing” section, where we can eliminate everything after it since our company is now to the left of where we’re at. If we continue this process, eventually we’ll reach “Roach-B-Gone”. We’ve just employed the logic of a Binary Search Tree.

Tree Basics

A basic tree structure.

Trees are data structures that employ a hierarchy that connect nodes to one another. They are non-linear and can store any type of data. Trees start at the root (above the root is 2) node which can be connected to many different nodes and form many paths. Trees follow a top-down hierarchy, where a node that points to another node it called a parent, and the node it points to is the child. In the example above, 2 is the parent to children 7 and 5, while 5 is the parent to child 9. The child nodes of 7 — (2,10,6) — are called siblings since they share the same parent. the node 4 is called a leaf because it has no children.

Some common examples of trees are the HTML DOM, or file and folder structures on a computer.

Binary Search Trees

A Binary Search Tree is a data structure that organizes our data in a specific configuration, allowing us to insert and search through our data quickly. The tree in the example above is NOT a valid Binary Search Tree. Binary Search Trees follow 2 specific rules:

  1. Each parent nodes can have a maximum of 2 child nodes.
  2. The left child of a parent node must be lesser than the parent, and the the right child must be greater. We’ll use numbers to represent this, but note that this can also be used with strings considering their alphabetical order.
A valid binary search tree.

Implementation

We’ll start by implementing the Node class, which by definition has a left and right reference to other nodes, and then we’ll implement insert and find.

JavaScript Implementation of Binary Search Tree

You’ll notice that I used recursion to implement the find and insert methods — you could also use iteration it you’d like.

Time Complexity

Binary Search Trees at best can have a time complexity of O(log n) for insertion and search. However, this is not guaranteed because not all Binary Search Trees are perfectly sorted.

As an example let’s consider a singly linked list. A singly linked list that is ordered from least to greatest is technically a binary search tree. The root is the smallest value, and all the “right” nodes are larger. If we needed to insert a new largest number, or search for the largest number, we’d need to search through every single node. In this case, our time complexity would be O(n). When implementing these trees, it’s important to pick a node near the midpoint of your data for your tree to work most efficiently.

Resources

--

--