Data Structures: Binary Search Trees Explained

Binary search trees allow us to efficiently store and update, in sorted order, a dynamically changing dataset. When binary search trees are balanced, average time complexity for insert and find is O(log n), which is very efficient as our dataset grows. Before we dive into the details of a binary search tree, let’s first quickly review trees. What are trees?

Trees are nonlinear data structures composed of nodes that hold data. These nodes are connected by edges that define a parent and child relationship. Trees are nonlinear in that they are not organized sequentially, instead they are organized through relationships or hierarchy. The first node of a tree is called the root node and it can have zero or more child nodes. A child node in a tree forms a subtree, where that child can have zero or more child nodes of its own, and so on (as you can see there’s a recursive approach to trees). To better visualize what a tree is you can think of a tree as a hierarchical org chart of a company, an animal classification tree in biology, or the Document Object Model (DOM).

What is a binary tree?

There are multiple types of trees, but we will focus on the binary tree. A binary tree is a type of tree in which each node has a maximum of two children. Binary trees can be:

• full: every node has either zero or two children. Nodes do not have only one child.
• complete: every level in the tree is fully filled with the possible exception of the last level, which should be filled from left to right.
• perfect: it is both full and complete and must have exactly 2^(n -1) nodes.

What is a binary search tree?

A binary search tree (BST) is a type of binary tree where every node follows a particular ordering property. This ordering property is true for all nodes n and it states that all left descendants <= n < all right descendants. What defines a node as less than or greater than another node depends on your data type.

As mentioned earlier, its time complexity has an average of O(log n) for insert and find as you need not go through each node in the tree. You can divide and conquer by leveraging subsets of the tree. For example, if we want to insert(19)into the following BST:

1. We will compare 19 to our root node. As 19 < 20, we can ignore all nodes to the right of our root.

2. Then 19 > 16 so we can ignore all nodes to the left of 16.

3. Finally 19 > 17 and 17 has zero children so we can add 19 to the right of 17.

Coding our binary search tree

Given that we now understand how BSTs work, let’s implement one in JavaScript. As stated earlier, a BST has a max of two children where one child is to the left of (less than) and one is to the right of (greater than) their parent.

We will build our BST with the use of a constructor, which is an object type that is leveraged to create many objects of the same type. A constructor will allow us to create multiple BSTs with the same properties and methods, which is very useful for creating our subtrees.

function BinarySearchTree (val) {
  this.value = val;
  this.left = null;
  this.right = null;
}

Our BST takes in one parameter, val, and when called with the new keyword it will assign the received parameter to the value property of the current instance. The current instance will have a left and right property, which will hold the nodes that are less than or greater than itself (in other words, its children). The left and right properties will eventually be assigned toBinarySearchTree instances.

Inserting a Node

Now that we have our BST constructor, let’s work on a simple method (no error handling) that will allow us to insert nodes into our tree. We will assume that we will not have any duplicates to insert. We will leverage our object’s prototype to define our methods in order to save memory. This means that all objects created from this constructor will point to one common prototype object; hence, we only store each method once in memory.

BinarySearchTree.prototype.insert = function (value) {
  let subtree = value < this.value ? 'left' : 'right';
  if (this[subtree]) {
    this[subtree].insert(value);
  } else {
    this[subtree] = new BinarySearchTree(value);
  }
};

The insert method takes in a value as a parameter, which is the value that we’re interested in adding to our tree. We use a ternary operator (we can also leverage an if statement) to compare the value passed in with our current node. At this stage, our current node is our root. For example, if we run let newTree = new BinarySearchTree(20), then when we run our insert method newTree.insert(25) our initial this.value will be equal to 20 (our root’s this.value). Since our value passed in is greater than this.value, subtree is evaluated to 'right' and we now know which direction to take in our tree.

We then check if our this['right'], which is equivalent to this.right, holds a truthy or falsy value. We evaluate it to false as this.right = null, which is falsy, and then we execute our else statement. Our else statement will assign this.right to a new instance of our BST, which will enable us to create a subtree with its own left and right properties.

Our tree now holds two nodes, let’s now add a third with the value of 21 by executing newTree.insert(21). The subtree variable in the insert method will be assigned 'right', but this time we will execute our block of code in our if statement (not our else statement) because this['right'] evaluates to true since this.right is no longer null (it's pointing to the 25’s node). We will now recurse by calling insert on 25’s node (we will continue to recursively compare 21 to every node until the if statement hits a falsy value, meaning our node’s this.right or this.left value is equal to null). When we recurse, this.value is equal to 25 and subtree is assigned 'left' as 21 < 25. We will then execute our code in our else statement as 25’s this.left is null and create a new instance of BST with this.value = 21.

Finding a Node

Determining if a node exists in our BST is very similar to our insert method. We want to recursively evaluate our value passed in against the value of our current node. Let’s call our method contains , which will return true if the value exists or false if it does not exist in our tree. The method will be simple and we will not account for error handling. Please see the below image for a step by step walkthrough of the contains method.

BinarySearchTree.prototype.contains = function (value) {
  if (value === this.value) {
    return true;
  }
  let subtree = value < this.value ? 'left' : 'right';
  if (this[subtree]) {
    return this[subtree].contains(value);
  } else {
    return false;
  }
};

We’ve now implemented a BST with insert and contains methods in JavaScript! Some additional methods that we can implement are delete, min, and max. These methods would be able to remove nodes from a tree and find the minimum and maximum values of a tree.