Binary Search Trees

What are they? And when are they useful.

This week I put some time aside to study and garner a deeper understanding of a certain data structure that we weren’t taught in bootcamp — but comes up quite often in interview practice questions: binary trees or more specifically binary search trees. This to me, was a completely new data structure although implemented using basic class methods and also functions similar to arrays or lists the overall knowledge I had was scarce.

So what are trees? And what are binary trees?

A tree is a simple set to display data. As programmers, we commonly see this when thinking about the DOM (Document Object Model) in HTML and Javascript. A basic set of data (or more commonly referred to as a node) that branches out (like a tree) to more data. Thus, a binary tree can be defined as a data structure that consists of nodes that each have upto two children. Each node contains data that can be easily iterated over and compared, such as integers.

When a new node is being inserted into the tree structure, it will first be compared to each node to decide where it should be placed on the tree.

Creating a binary tree class is actually quite simple:

class Node {
constructor(value){
this.value = value } 
}
class BinarySearchTree{
constructor(){
this.values = [] } 
}

But what makes binary trees unique and what are they used for?

Well in computing, binary trees are used in two very different ways. First, as a means of accessing nodes based on some value associated with each node. Binary trees labelled this way are used to implement binary search trees and binary heaps; used for efficient searching and sorting.

Let’s look at some practical uses for binary trees to help put this into perspective.

Binary trees are known to be extremely useful because of the speed at which nodes can be inserted, found, deleted and reversed. We’ve learned time and again that arrays are pretty quick when it comes to pushing data in (at the end) and removing data (at the end). However, because arrays come with default indices, shifted data to the beginning of an array causes an entire shift to the indices in the array.

For example:

let arr = [6, 9, 7, 3, 5]
// index   0  1  2  3  4
arr.unshift(8) 
    arr = [8, 6, 9, 7, 3, 5]
// index   0  1  2  3  4  5

Here, just adding one integer to the beginning shifted all the indices throughout the array. Needless to say, time and space complexity wise: not so ideal.

Binary trees however excel at this department. The time complexity of a binary tree search is equivalent to the height of the tree. Searching, inserting and deleting all have a O(log n) time complexity.

A very common use for binary trees are in file compression. Data compression code uses binary trees as their main source, due to its quick properties of disassembling. Other instances where binary trees are quite useful include the implementation of a routing table in router, expression parsers and solvers and expression evaluation.

Although a little foreign at first, binary trees are fun to implement and play around with. Being able to apply basic functionality such as insertion, getting a certain value at a specified index, changing a value can really help to sharpen your data structure know.